A CHARACTERIZATION OF 1-TRIANGLE GRAPHS
Abstract
A graph is called 1-triangle if for each maximal independent set I, each edge of this graph with both end vertices not belonging to I forms exactly one triangle with a vertex from the set I. We have obtained a structural characterization of 1-triangle graphs which implies a polynomial time recognition algorithm for this class of graphs.
About the Authors
P. A. IRZHAVSKI
Belarusian State University
Belarus
Belarus
Yu. A. KARTYNNIK
Belarusian State University
Belarus
Belarus
Yu. L. ORLOVICH
Belarusian State University
Belarus
Belarus
References
1. Лекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990. – 384 с.
2. DeTemple, D. Graphs associated with triangulations of lattice polygons / D. DeTemple, J. M. Robertson // J. Austral. Math. Soc. Ser. A. – 1989. – Vol. 47, N 3. – P. 391–398.
3. DeTemple, D. Partition graphs / D. DeTemple, F. Harary, J. Robertson // Soochow J. Math. – 1987. – Vol. 13, N 2. – P. 121–129.
4. On the recognition of general partition graphs / T. Kloks [et al.] // Lect. Notes Comput. Sci. – 2003. – Vol. 2880. – P. 273–283.
5. McAvaney, K. A characterization and hereditary properties for partition graphs / K. McAvaney, J. Robertson, D. De- Temple // Discrete Math. – 1993. – Vol. 113, N 1–3. – P. 131–142.
6. Miklavič, S. Equistable graphs, general partition graphs, triangle graphs, and graph products / S. Miklavič, M. Milanič // Discrete Appl. Math. – 2011. – Vol. 159, N 11. – P. 1148– 1159.
7. Cerioli, M. R. Structural results for general partition, equistable and triangle graphs / M. R. Cerioli, T. L. Martins // Electron. Notes Discrete Math. – 2015. – Vol. 49. – P. 713–718.
8. Recent examples in the theory of partition graphs / D. W. DeTemple [et al.] // Discrete Math. – 1993. – Vol. 113, N 1–3. – P. 255–258.
9. Зверович, И. Е. О графах разбиений / И. Е. Зверович, Ю. Л. Орлович // Докл. НАН Беларуси. – 2002. – Т. 46, № 4. – С. 38–42.
10. Orlovich, Yu. L. Independent domination in triangle graphs / Y. L. Orlovich, I. E. Zverovich // Electron. Notes Discrete Math. – 2007. – Vol. 28. – P. 341–348.
11. Mahadev, N. V. R. Equistable graphs / N. V. R. Mahadev, U. N. Peled, F. Sun // J. Graph Theory. – 1994. – Vol. 18, N 3. – P. 281–299.
12. Levit, V. E. Equistable simplicial, very well-covered, and line graphs / V. E. Levit, M. Milanič // Discrete Appl. Math. – 2014. – Vol. 165. – P. 205–212.
13. Milanič, M. Equistarable graphs and counterexamples to three conjectures on equistable raphs / M. Milanič, N. Trotignon // ArXiv e-prints (arXiv:1407.1670) [Electronic resource]. – Mode of access: http://arxiv.org/abs/1407.1670. – Date of access: 17.05.2016.
14. Boros, E. On equistable, split, CIS, and related classes of graphs / E. Boros, V. Gurvich, M. Milanič // ArXiv e-prints (arXiv:1505.05683) [Electronic resource]. – Mode of access: http://arxiv.org/abs/1505.05683. – Date of access: 17.05.2016.
15. Sampathkumar, E. The neighbourhood number of a graph / E. Sampathkumar, P. S. Neeralagi // Indian J. Pure Appl. Math. – 1985. – Vol. 16. – P. 126–132.
16. Sampathkumar, E. Independent, perfect and connected neighbourhood numbers of a graph / E. Sampathkumar, P. S. Neeralagi // J. Combin. Inf. Syst. Sci. – 1994. – Vol. 19, N 3–4. – P. 139–145.
17. Bollobás, B. Graph-theoretic parameters concerning domination, independence, and irredundance / B. Bollobás, E. J. Cockayne // J. Graph Theory. – 1979. – Vol. 3, N 3. – P. 241– 249.
18. Картынник, Ю. А. Доминантно-треугольные графы и графы верхних границ / Ю. А. Картынник, Ю. Л. Орлович // Докл. НАН Беларуси. – 2014. – Т. 58, № 1. – С. 16–25.
19. When are chordal graphs also partition graphs? / C. Anbeek [et al.] // Australas. J. Combin. – 1997. – Vol. 16. – P. 285–293.
20. Simplicial graphs / G. A. Cheston [et al.] // Congr. Numer. – 1988. – Vol. 67. – P. 105–113. 21. Cheston, G. A. A survey of the algorithmic properties of simplicial, upper bound and middle graphs / G. A. Cheston, T. S. Jap // J. Graph Algorithms Appl. – 2006. – Vol. 10, N 2. – P. 159–190.
Review
Views: 777
Email this article 