Research ArticleOpen AccessGoogle Scholar indexed
A Remark on the Characterization of Triangulated Graphs
Department of Mathematics, Faculty of Sciences of Monastir, Monastir, Tunisia
Department of Mathematics, College of Sciences, Taibah University, Madina, Saudi Arabia
- 1 Department of Mathematics, Faculty of Sciences of Monastir, Monastir, Tunisia
- 2 Department of Mathematics, College of Sciences, Taibah University, Madina, Saudi Arabia
Open Journal of Discrete Mathematics·Volume 13 (2023)·Pages 55–62·Published 18 April 2023·DOI10.4236/ojdm.2023.132006
Copy link · social · email
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.
KeywordsTriangulated GraphsPerfect SetClique
- 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
- 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.
- Bergec, C. (1961) Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starrsind. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 114.
- 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
- Buneman, P. (1974) A Characterization of Rigid Circuit Graphs. Discrete Mathematics, 9, 205-212. https://doi.org/10.1016/0012-365X(74)90002-8
- Fulkerson, D.R. and Gross, O.A. (1974) Incidence Matrices and Interval Graphs. Pacific Journal of Mathematics, 15, 5335-855.
- 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
- 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
- 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
- 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
- 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
- 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
- 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