danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"dan-325Research ArticleМАТЕМАТИКАMATHEMATICSХАРАКТЕРИЗАЦИЯ 1-ТРЕУГОЛЬНЫХ ГРАФОВA CHARACTERIZATION OF 1-TRIANGLE GRAPHSИРЖАВСКИЙП. А.IRZHAVSKIP. A.irzhavski@bsu.byКАРТЫННИКЮ. А.KARTYNNIKYu. A.kartynnik@bsu.byОРЛОВИЧЮ. Л.ORLOVICHYu. L.orlovich@bsu.byБелорусский государственный университетBelarusian State University2016281020166041724Copyright © ИРЖАВСКИЙ П.А., КАРТЫННИК Ю.А., ОРЛОВИЧ Ю.Л., 20162016ИРЖАВСКИЙ П.А., КАРТЫННИК Ю.А., ОРЛОВИЧ Ю.Л.IRZHAVSKI P.A., KARTYNNIK Y.A., ORLOVICH Y.L.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/325

Граф называется 1-треугольным, если для любого максимального независимого множества I этого графа каждое ребро графа, не инцидентное ни одной вершине из I, образует единственный треугольник с вершиной из множества I. В работе получена структурная характеризация класса 1-треугольных графов, которая влечёт полиномиальный алгоритм их распознавания.

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.

треугольный графрёберно-симплициальный графхарактеризациянезависимое множествосовершенное окрестностное множествоtriangle graphedge simplicial graphcharacterizationindependent setperfect neighbourhood setReferencesЛекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990. – 384 с.Лекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990. – 384 с.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.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.DeTemple, D. Partition graphs / D. DeTemple, F. Harary, J. Robertson // Soochow J. Math. – 1987. – Vol. 13, N 2. – P. 121–129.DeTemple, D. Partition graphs / D. DeTemple, F. Harary, J. Robertson // Soochow J. Math. – 1987. – Vol. 13, N 2. – P. 121–129.On the recognition of general partition graphs / T. Kloks [et al.] // Lect. Notes Comput. Sci. – 2003. – Vol. 2880. – P. 273–283.On the recognition of general partition graphs / T. Kloks [et al.] // Lect. Notes Comput. Sci. – 2003. – Vol. 2880. – P. 273–283.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.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.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.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.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.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.Recent examples in the theory of partition graphs / D. W. DeTemple [et al.] // Discrete Math. – 1993. – Vol. 113, N 1–3. – P. 255–258.Recent examples in the theory of partition graphs / D. W. DeTemple [et al.] // Discrete Math. – 1993. – Vol. 113, N 1–3. – P. 255–258.Зверович, И. Е. О графах разбиений / И. Е. Зверович, Ю. Л. Орлович // Докл. НАН Беларуси. – 2002. – Т. 46, № 4. – С. 38–42.Зверович, И. Е. О графах разбиений / И. Е. Зверович, Ю. Л. Орлович // Докл. НАН Беларуси. – 2002. – Т. 46, № 4. – С. 38–42.Orlovich, Yu. L. Independent domination in triangle graphs / Y. L. Orlovich, I. E. Zverovich // Electron. Notes Discrete Math. – 2007. – Vol. 28. – P. 341–348.Orlovich, Yu. L. Independent domination in triangle graphs / Y. L. Orlovich, I. E. Zverovich // Electron. Notes Discrete Math. – 2007. – Vol. 28. – P. 341–348.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.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.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.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.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.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.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.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.Sampathkumar, E. The neighbourhood number of a graph / E. Sampathkumar, P. S. Neeralagi // Indian J. Pure Appl. Math. – 1985. – Vol. 16. – P. 126–132.Sampathkumar, E. The neighbourhood number of a graph / E. Sampathkumar, P. S. Neeralagi // Indian J. Pure Appl. Math. – 1985. – Vol. 16. – P. 126–132.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.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.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.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.Картынник, Ю. А. Доминантно-треугольные графы и графы верхних границ / Ю. А. Картынник, Ю. Л. Орлович // Докл. НАН Беларуси. – 2014. – Т. 58, № 1. – С. 16–25.Картынник, Ю. А. Доминантно-треугольные графы и графы верхних границ / Ю. А. Картынник, Ю. Л. Орлович // Докл. НАН Беларуси. – 2014. – Т. 58, № 1. – С. 16–25.When are chordal graphs also partition graphs? / C. Anbeek [et al.] // Australas. J. Combin. – 1997. – Vol. 16. – P. 285–293.When are chordal graphs also partition graphs? / C. Anbeek [et al.] // Australas. J. Combin. – 1997. – Vol. 16. – P. 285–293.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.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.

The authors declare that there are no conflicts of interest present.