A Remark on the Characterization of Triangulated Graphs

Hatem Najar^1,2, Riadh Gargouri²

¹Department of Mathematics, Faculty of Sciences of Monastir, Monastir, Tunisia.
²Department of Mathematics, College of Sciences, Taibah University, Madina, Saudi Arabia.

DOI: 10.4236/ojdm.2023.132006                

Abstract

In this study, we consider the problem of triangulated graphs. Precisely we give a necessary and sufficient condition for a graph to be triangulated. This gives an alternative characterization of triangulated graphs. Our method is based on the so-called perfectly nested sequences.

Keywords

Triangulated Graphs, Perfect Set, Clique

1. Introduction

It is well known that graph theory provides simple, but powerful tools for constructing models and solving numerous types of interdisciplinary problems and possesses a wide range of applications [1] . Indeed graphs and graph theory can be used in several areas such as software designs, computer networks, social networks, communications networks, information networks, transportation networks, biological networks, managerial problems and others.

In 1736, the problem of the Königsberg bridges was considered as the first problem that laid the foundation of graph theory. Since the start of interest in this well-known problem several questions and problems have arisen.

Regarding the topic of this note, triangulated graphs form an important class among graphs. Since the end of the last century, a lot of work has been done in the theory of triangulated graphs (which we will define properly below). In some references triangulated graphs are variously called rigid circuit graphs [2] , chordal graphs [3] or monotone transitive graphs, like in [4] .

Triangulated graphs can be characterized in a number of different ways. See [2] [4] [5] [6] [7] [8] . We recall that a vertex v of a graph G is said to be simplicial if v together with all its adjacent vertices induces a clique in G. An ordering $v_1\mathrm{,}{v}_2\mathrm{,}\cdots ,v_n$ of all the vertices of G forms a perfect elimination ordering of G if each $v_i\mathrm{,1}\le i\le n$ , is simplicial in the subgraph induced by $v_i\mathrm{,}{v}_{i+1}\mathrm{,}\cdots \mathrm{,}{v}_n$ . In [2] , we find a necessary condition for a graph G to be triangulated which is the existence of simplicial vertex. In [6] , Fulkerson and Gross, state that a graph G is triangulated if, and only if, it has a perfect elimination ordering. Precisely, Fulkerson and Gross showed that the class of triangulated graphs is exactly the class of graphs having perfect elimination orderings. Thus when the input graph G is not triangulated, no perfect elimination of it exists. Rose et al. in [9] treat the question of triangulated graphs and also give several characterizations of minimal triangulations. In [10] the author gives a new representation of a triangulated graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph.

At the end of this section we mention that triangulated graphs have applications in several areas such as computer vision [11] , the solution of sparse symmetric systems of linear equations [12] , database management systems [13] and knowledge-based systems [14] . At the end of the paper, we collect two main consequences of triangulated graphs. Another consequence of triangulated graphs is the problem of finding a maximum clique. Indeed, in a triangulated graph we get the answer in polynomial time, while the same problem for general graphs is NP-complete. More generally, a triangulated graph can have only linearly many maximal cliques, while non-chordal graphs may have exponentially many [15] .

Basic Concept of Graph Theory

In this section, we will enumerate and explain the basic definitions and the necessary terminology to make use of graph theory. There is a great variety in how different authors presented the basic definitions of the graph theory. Indeed there are many roughly equivalent definitions of a graph.

Most commonly, a graph G is defined as an ordered pair $\left(V\mathrm{,}E\right)$ , where $V=\left\{v_1\mathrm{,}\cdots \mathrm{,}{v}_n\mathrm{,}\cdots \right\}$ is called the graph’s vertex-set or some times the node set and $E=\left\{e_1\mathrm{,}\cdots \mathrm{,}{e}_m\mathrm{,}\cdots \right\}\subset \left\{\left\{x\mathrm{,}y\right\}\mathrm{<mo>\; |\; </mo>}x\mathrm{,}y\in V\right\}$ is called the edges set.

Given a graph G, we often denote the vertexset by $V\left(G\right)$ and the edgeset by $E\left(G\right)$ . To visualize a graph as described above, we draw dots corresponding to vertices $v_1\mathrm{,}\cdots \mathrm{,}{v}_n\mathrm{,}\cdots$ . Then, for all $i\mathrm{,}j\in \left\{\mathrm{1,}\cdots \mathrm{,}n\mathrm{,}\cdots \right\}$ imagine a line between the dots corresponding to vertices $v_i\mathrm{,}{v}_j$ if and only if there exists an edge $\left\{v_i\mathrm{,}{v}_j\right\}\in E$ . Note that the placement of the dots is generally unimportant; many different pictures can represent the same graph as it is given in the example below Figure 1.

A subgraph is a concept akin to the subset. A subgraph has a subset of the vertex set $A\subseteq V$ , a subset $E\left(A\right)=\left\{\left\{x\mathrm{,}y\right\}\in E\mathrm{<mo>\; :\; </mo>}x\mathrm{,}y\in A\right\}$ of the edge set E, and each edge’s endpoints in the larger graph has the same edges in the subgraph. We denote it by $G\left(A\right)=\left(A\mathrm{,}E\left(A\right)\right)$ .

Figure 1. Two different representations of same graph.

Two vertices are said to be adjacent if there is an edge joining them. Given $x\in V$ , the set of all adjacent vertices in G is denoted by $Adj\left(x\right)$ ,

$Adj\left(x\right)=\left\{y\in V\mathrm{,}\left\{x\mathrm{,}y\right\}\in E\right\}\mathrm{.}$ (1)

The word incident has two meanings: On the one hand, an edge e is said to be incident to a vertex v if v is an endpoint of e. On the other hand, two edges are also incident to each other if both are incident to the same vertex. A set C of vertices is a clique if every pair of vertices in C are adjacent. A clique of a graph G is a complete subgraph of G.

A path is a sequence of edges $\langle e_1\mathrm{,}\cdots \mathrm{,}{e}_N\rangle$ (also denoted $\left(v_1\mathrm{,}\cdots \mathrm{,}{v}_n\right)$ such that $e_i$ is adjacent to $e_{i+1}$ for all i from 1 to $N-1$ , $e_i$ relates $v_i$ to $v_{i+1}$ . Two vertices are said to be connected if there is a path connecting them. A cycle is a path such that the last edge of the path is adjacent to the first and visits each vertices once (in some references they call this elementary cycle).

In a simple graph each edge connects two different vertices and no two edges connect the same pair of vertices. Multi-graphs may have multiple edges connecting the same two vertices. An edge that connects a vertex to itself is called a loop. Two graphs G and G' are said to be isomorphic if there is a one-to-one function from (or, if you prefer, one-to-one correspondence between) the vertex set of G to the vertex set of G' such that two vertices in G are adjacent if and only if their images in G' are adjacent. Technically, the multiplicity of the edges must also be preserved, but our definition suffices for simple graphs, which are graphs without multiple edges or loops.

Definitions

A graph is called triangulated if every cycle of length greater than three possesses a chord, i.e. an edge joining two non-consecutive vertices of the cycle. A vertex x of a graph $G=\left(V\mathrm{,}E\right)$ is called perfect in G if $Adj\left(x\right)=\varnothing$ or $\left(\left\{x\right\}\cup Adj\left(x\right)\right)$ is a clique. For $A\subseteq V$ , we denote by $P\left(A\right)$ the set of all perfect vertices of A in $G\left(A\right)$ (Figure 2).

Let $G=\left(V\mathrm{,}E\right)$ , be a graph. A sequence ${\left(U_n\right)}_{n\in \mathbb{N}}$ of subsets of $\mathcal{P}\left(V\right)$ , is said to be perfectly nested on $G=\left(V\mathrm{,}E\right)$ , if it satisfies the following three conditions

1) $U_0=V$ .

2) $\forall n\in \mathbb{N}$ ,

$U_{n+1}\subseteq U_n\mathrm{.}$

3) $\forall n\in \mathbb{N}$ , $P\left(U_n\right)\ne \varnothing$ , and

$U_n\backslash U_{n+1}\subseteq P\left(U_n\right)$ .

Figure 2. Perfect vertices.

We say that the sequence is stationary perfectly nested, if furthermore the three last conditions, there exists $n_0\ge 0$ such that we have $P\left(U_n\right)=U_n$ , for any $n\ge n_0$ .

2. The Results

Proposition 1 Let $G=\left(V\mathrm{,}E\right)$ be a graph and $A\subset P\left(X\right)$ . Then the following items are equivalents:

1) $G=\left(V\mathrm{,}E\right)$ is triangulated;

2) $G=\left(V\backslash A\right)$ is triangulated.

Proof. It is clear that 1) implies 2).

For the other sense, let us consider $A\ne \varnothing$ . Let $C=\left(v_1\mathrm{,}\cdots \mathrm{,}{v}_n\right)$ be a cycle in $G=\left(V\mathrm{,}E\right)$ . There are two possibilities [(a)].

1) If $C\subseteq V\backslash A$ , then C has a chord.

2) If $C\cap A\ne \varnothing$ , there exists $i_0\in \left\{\mathrm{1,}\cdots \mathrm{,}n\right\}$ such that $v_{i_0}\in A$ . As $v_{i_0}$ is a perfect vertex, then $Adj\left(v_{i_0}\right)\cap C$ is a clique and so, C has a chord. So $G=\left(V\mathrm{,}E\right)$ is triangulated.

Theorem 2 Let $G=\left(V\mathrm{,}E\right)$ be a graph. Suppose that there exists a perfectly nested sequence on $G=\left(V\mathrm{,}E\right)$ . Then $G=\left(V\mathrm{,}E\right)$ is a triangulated graph.

Proof. Let $C=\left(v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right)\mathrm{,}n\ge 4$ , be a cycle in the graph $G=\left(V\mathrm{,}E\right)$ . Let ${\left(U_n\right)}_n$ a perfectly nested sequences. There exists $n\in \mathbb{N}$ , such that

$C\subseteq U_n,C⊈U_{n+1}.$

So,

$C\cap P\left(U_n\right)\ne \varnothing \mathrm{.}$

This ensures that there exists a perfect vertices $x\in C\cap G\left(U_n\right)$ . So C has a chord.

When V is infinite let us notice that we can construct triangulated graphs which do not have a perfectly nested sequence. Indeed for $V=\mathbb{Z}$ and $E=\left\{\left\{n\mathrm{,}n+1\right\}\mathrm{,}n\in \mathbb{Z}\right\}$ , $G=\left(V\mathrm{,}E\right)$ is triangulated and $P\left(V\right)=\varnothing$ .

Theorem 3 Let $G=\left(V\mathrm{,}E\right)$ be a graph, with V being a finite set. Then, $G=\left(V\mathrm{,}E\right)$ is triangulated if and only if there exists a stationary perfectly nested sequence on $G=\left(V\mathrm{,}E\right)$ .

Proof. For the proof, we need the following two basic lemmas:

[4] Let $G=\left(V\mathrm{,}E\right)$ be a triangulated finite graph. Then $P\left(V\right)=\varnothing$ . The proof of the last lemma is given in [4] by using the notion of the minimal separators and elimination process. From a different point of view, we can see this by noting that if we suppose that $P\left(V\right)=\varnothing$ , starting with a non perfect point x it has necessary two adjacent points $x_1\mathrm{,}{y}_1$ which themselves are non adjacent to each others. As V is a finite set, a typical end of the process should be in the form of Figure 3. At this step, as no point can be adjacent to a single point being a non perfect point it is adjacent to more than two points. This leads forcibly the existence of a non-chordal cycle of length of more than 3. So $G=\left(V\mathrm{,}E\right)$ is not triangulated. Let $G=\left(V\mathrm{,}E\right)$ be a connected graph. Let $A\subset P\left(V\right)$ . Then, $G=\left(V\backslash A\right)$, is also a connected graph.

Proof. Let $A\subseteq P\left(V\right)$ , and $v_1\mathrm{,}{v}_n\in V\backslash A$ . As $G=\left(V\mathrm{,}E\right)$ is a connected graph, there exists a path $P=\left(v_1\mathrm{,}\cdots \mathrm{,}{v}_n\right)$ in $G=\left(V\mathrm{,}E\right)$ , for any $v_{i_0}\in A\cap P$ , as $v_{i_0-1}$ and $v_{i_0+1}$ are in $Adj\left(v_{i_0}\right)$ , we get that $v_{i_0-1}\in Adj\left(V_{i_0+1}\right)$ , by the definition of $v_{i_0}$ being a perfect point. So we get a path $P^{\prime }=\left(v_1,\cdots ,v_{i_0-1},v_{i_0+1},\cdots ,v_n\right)$ in $G=\left(V\backslash A\mathrm{,}E\left(A\right)\right)$ .

Let us start by the proof of the necessary condition. By Lemma 2(`)@ we know that when $G=\left(V\mathrm{,}E\right)$ is triangulated, then $P\left(V\right)\ne \varnothing$ ; For $V_1⊈P\left(V\right)$ , we set

$U_2=U_1\backslash V_1\mathrm{,}with{U}_1=V\mathrm{.}$

By Proposition 1, $G\left(U_2\mathrm{,}E\left(U_2\right)\right)$ is a triangulated graph, so $P\left(U_2\right)\ne \varnothing$ . Let $V_2\subseteq P\left(U_2\right)$ , we set

$U_3=U_2\backslash V_2.$

In the same way we construct the perfectly nested sequence. As the set V is finite by assumption we get the stationarity property using the result of Lemma 2, as at the end it remains only one or two perfect points.

For the sufficient condition it is given by Theorem 2.

Below we give an example where using our result we get the answer to the question of triangulated graph after only three steps.

Let us end this section with the following remark. In this particular case, if we take a perfectly nested sequence in Theorem 3 with the property that for any $1\le i<n$ , $\left|U_i\backslash U_{i+1}\right|=1$ , $\left|U_n\right|=1$ we get the characterization given in [4] , by taking

$\alpha \mathrm{<mo>\; :\; </mo>}\left\{\mathrm{1,}\cdots \mathrm{,}n\right\}\mapsto V\mathrm{.}$

${\alpha }^{-1}\left(U_i\backslash U_{i+1}\right)=\left\{i\right\},{\alpha }^{-1}\left(U_n\right)=\left\{n\right\}.$

Figure 3. Triangulated graph.

3. Some Consequences of Triangulation

For completeness, below we collect some possible implications of our main result. In addition to the consequence given in the introduction which concerns the answer in polynomial time to some problems for triangulated graphs, the same problem for general graphs is NP-complete. Below we collect two more consequences of triangulated graphs.

3.1. Directed Acyclic Graphs

An orientation D of a finite graph G with n vertices is obtained by considering a fixed direction, either $x\to y$ or $y\to x$ , on every edge $\left\{xy\right\}$ of G.

We call an orientation D acyclic if there does not exist any directed cycle. A directed graph having no directed cycle is known as a directed acyclic graph, we write DAG for short. DAGs provide frequently used data structures in computer science for encoding dependencies. The topological ordering is another way to describe a DAG. A topological ordering of a directed graph $G=\left(V\mathrm{,}E\right)$ is an ordering of its vertices as $v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n$ such that for every arc $v_i\to v_j$ , we have $i<j$ .

Let us consider an acyclic orientation D of G. An edge of D, is said to be dependent (in D) if its reversal creates a directed cycle in the resulted orientation. Note that $v_i\to v_j$ is a dependent arc if and only if there exists a directed walk of length at least two from $v_i$ to $v_j$ . We denote by $d\left(D\right)$ , the number of dependent arcs in D. A graph G is called fully orientable if it has an acyclic orientation with exactly d dependent arcs for every number d between $dmin\left(G\right)$ and $dmax\left(G\right)$ , the minimum and the maximum values of $d\left(D\right)$ overall acyclic orientations D of G. An acyclic orientation with 6 dependents arcs (Figure 4).

In [16] , the authors show that all chordal graphs are fully orientable. Let us denote the complete r-partite graph each of whose partite sets has n vertices by $K_r\left(n\right)$ . As it is also known [17] that $K_r\left(n\right)$ is not fully orientable when $r\ge 3$ and $n\ge 2$ . One deduces that the acyclic orientation $K_3\left(2\right)$ given in the example is not a triangulated graph. If we consider the graph of example 3, as it is a triangulated graph we deduce that it is a fully orientable graph.

Figure 4. An acyclic orientation.

3.2. Chromatic Number

A graph coloring is an assignment of labels, called colors, to the vertices of a graph such that no two adjacent vertices share the same color.

1) A Clique number $\omega \left(G\right)$ , is the maximum size of a clique in G.

2) A Chromatic number $\chi \left(G\right)$, is the minimum coloring number.

For a general graph G, we have

$\chi \left(G\right)\ge \omega \left(G\right)\mathrm{.}$ (2)

For triangulated graphs, we have equality instead of inequality in Equation (2).

Acknowledgement

The authors would like to express my deep gratitude to my colleague Professor F. Khlif for valuable comments and interesting discussions during the current work which improve the quality of the paper.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Blair, J.R.S. and Peyton, B.W. (1993) An Introduction to Chordal Graphs and Clique Trees. In: George, J.A., Gilbert, J.R. and Liu, J.W.H., Eds., Graph Theory and Sparse Matrix Computations (381), IMA Volumes in Mathematics and Its Applications, Vol. 56, Springer Verlag, Berlin, 1-30. https://doi.org/10.1007/978-1-4613-8369-7_1
[2]	Dirac, G.A. (1993) On Rigid Circuit Graphs. In: George, J.A., Gilbert, J.R. and Liu, J.W.H., Eds., Graph Theory and Sparse Matrix Computations (381), Vol. 25, Springer Verlag, Berlin, 71-76.
[3]	Bergec, C. (1961) Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starrsind. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 114.
[4]	Rose, D.J. (1970) Triangulated Graphs and the Elimination Process. Journal of Mathematical Analysis and Applications, 32, 597-609. https://doi.org/10.1016/0022-247X(70)90282-9
[5]	Buneman, P. (1974) A Characterization of Rigid Circuit Graphs. Discrete Mathematics, 9, 205-212. https://doi.org/10.1016/0012-365X(74)90002-8
[6]	Fulkerson, D.R. and Gross, O.A. (1974) Incidence Matrices and Interval Graphs. Pacific Journal of Mathematics, 15, 5335-855.
[7]	Gavril, F. (1965) The Intersection Graphs of Subtrees in Trees Are Exactly the Chordal Graphs. Journal of Combinatorial Theory, Series B, 16, 47-56. https://doi.org/10.1016/0095-8956(74)90094-X
[8]	Habib, M. and Limouzy, V. (2009) On Some Simplicial Elimination Schemes for Chordal Graphs. Electronic Notes in Discrete Mathematics, 32, 125-132. https://doi.org/10.1016/j.endm.2009.02.017
[9]	Rose, D.J., Tarjan, R.E. and Lueker, G.S. (1976) Algorithmic Aspects of Vertex Elimination on Graphs. SIAM Journal on Computing, 5, 266-283. https://doi.org/10.1137/0205021
[10]	Ibarra, L. (2009) The Clique-Separator Graph for Chordal Graphs. Discrete Applied Mathematics, 157, 1737-1749. https://doi.org/10.1016/j.dam.2009.02.006
[11]	Chung, F.R.K. and Mumford, D. (1994) Chordal Completions of Planar Graphs. Journal of Combinatorial Theory, Series B, 31, 96-106. https://doi.org/10.1006/jctb.1994.1056
[12]	Rose, D.J. (1972) A Graph-Theoretic Study of the Numerical Solution of Sparse Positive Definite Systems of Linear Equations. In: Graph Theory and Computing, Academic Press, New York, 183-217. https://doi.org/10.1016/B978-1-4832-3187-7.50018-0
[13]	Tarjan, R.E. and Yannakakis, M. (1984) Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM Journal on Computing, 13, 566-579. https://doi.org/10.1137/0213035
[14]	England, R.E., Blair, J.R.S. and Thomason, M.G. (1991) Independent Computations in a Probabilistic Knowledge-Based System. Technical Report CS-91-128, Department of Computer Science, The University of Tennessee, Knoxville.
[15]	Asdre, K. and Nikolopoulos, S.D. (2007) NP-Completeness Results for Some Problems on Subclasses of Bipartite and Chordal Graphs. Theoretical Computer Science, 381, 248-259. https://doi.org/10.1016/j.tcs.2007.05.012
[16]	Lai, H.-H. and Lih, K.-W. (2015) Chordal Graphs Are Fully Orientable. Ars Combinatoria,122, 289-298.
[17]	Chang, G.J., Lin, C.-Y. and Tong, L.-D. (2009) Independent Arcs of Acyclic Orientations of Complete r-Partite Graphs. Discrete Mathematics, 309, 4280-4286. https://doi.org/10.1016/j.disc.2009.01.002