ХАРАКТЕРИЗАЦИЯ 1-ТРЕУГОЛЬНЫХ ГРАФОВ
Аннотация
Граф называется 1-треугольным, если для любого максимального независимого множества I этого графа каждое ребро графа, не инцидентное ни одной вершине из I, образует единственный треугольник с вершиной из множества I. В работе получена структурная характеризация класса 1-треугольных графов, которая влечёт полиномиальный алгоритм их распознавания.
Об авторах
П. А. ИРЖАВСКИЙ
Белорусский государственный университет
Беларусь
Беларусь
Ю. А. КАРТЫННИК
Белорусский государственный университет
Беларусь
Беларусь
Ю. Л. ОРЛОВИЧ
Белорусский государственный университет
Беларусь
Беларусь
Список литературы
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.
Рецензия
Просмотров: 805
Послать статью по эл. почте 