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.
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
