Том 29, номер 1, 2022 г., Стр. 46-55
УДК 519.17
А. В. Пяткин, О. И. Черных
О максимальном числе открытых треугольников в графах с одинаковым числом вершин и рёбер
Аннотация:
Открытым треугольником (ОТ) называется трёхвершинный подграф с двумя рёбрами, т. е. индуцированный путь длины 2. В работе получена формула для максимально возможного числа ОТ в $n$-вершинных графах c $n$ рёбрами и дана полная характеризация графов, на которых достигается этот максимум.
Ил. 2, библиогр. 10.
Ключевые слова: открытые треугольники, индуцированные подграфы, унициклические графы.
DOI: 10.33048/daio.2022.29.723
Пяткин Артём Валерьевич 1,2
Черных Оксана Ильинична 2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: artem@math.nsc.ru, o.chernykh@g.nsu.ru
Статья поступила 26 июля 2021 г.
После доработки — 27 сентября 2021 г.
Принята к публикации 28 сентября 2021 г.
Литература
[1] Milo R., Shen-Orr S., Itzkovitz S., Kashtan N., Chklovskii D., Alon U. Network motifs: Simple building blocks of complex networks // Science. 2002. V. 298. P. 824–827.
[2] Robins G. A tutorial on methods for the modeling and analysis of social network data // J. Math. Psychol. 2013. V. 57. P. 261–274.
[3] Schank T., Wagner D. Finding, counting and listing all triangles in large graphs, an experimental study // Lect. Notes Comput. Sci. 2005. V. 3503. P. 606–609.
[4] Batagelj V., Mrvar A. A subquadratic triad census algorithm for large sparse networks with small maximum degree // Social Networks. 2001. V. 23. P. 237–243.
[5] Johnsen E. C. Structure and process: agreement models for friendship formation // Social Networks. 1986. V. 8. P. 257–306.
[6] Moody J. Matrix methods for calculating the triad census // Social Networks. 1998. V. 20. P. 291–299.
[7] Wasserman S., Faust K. Social network analysis. Camb. Univ. Press, 1994.
[8] Goodman A. W. On sets of acquaintances and strangers at any party // Amer. Math. Monthly. 1959. V. 66, No. 9. P. 778–783.
[9] Sauve L. On chromatic graphs // Amer. Math. Monthly. 1961. V. 68. P. 107–111.
[10] Pyatkin A., Lykhovyd E., Butenko S. The maximum number of induced open triangles in graphs of a given order // Optim. Lett. 2018. V. 13, No. 8. P. 1927–1935.
