Об экстремальных по числу открытых треугольников графах с малым числом рёбер

Об экстремальных по числу открытых треугольников графах с малым числом рёбер

Пяткин А. В.
Дискретный анализ и исследование операций, 32, 2, 107-121 (2025)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2025.32.830

Аннотация:

Открытым треугольником (ОТ) в неориентированном графе называется индуцированный подграф из трёх вершин ровно с двумя рёбрами. Рассматривается класс графов, в котором числа вершин и рёбер отличаются на фиксированную константу c. Получена полная характеризация экстремальных по числу ОТ графов в таком классе с не менее чем $c + 7$ вершинами. 

Ил. 1, библиогр. 12.

Литература:
  1. Johnsen E. C. Structure and process: Agreement models for friendship formation // Soc. Networks. 1986. V. 8, No. 3. P. 257–306.
     
  2. Moody J. Matrix methods for calculating the triad census // Soc. Netw. 1998. V. 20, No. 4. P. 291–299.
     
  3. Wasserman S., Faust K. Social network analysis: Methods and applications. Cambridge: Camb. Univ. Press, 1994. 826 p. (Struct. Anal. Soc. Sci.; V. 8). DOI: 10.1017/cbo9780511815478.
     
  4. Batagelj V., Mrvar A. A subquadratic triad census algorithm for large sparse networks with small maximum degree // Soc. Netw. 2001. V. 23, No. 3. P. 237–243.
     
  5. 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.
     
  6. Robins G. A tutorial on methods for the modeling and analysis of social network data // J. Math. Psychol. 2013. V. 57. P. 261–274.
     
  7. Schank T., Wagner D. Finding, counting and listing all triangles in large graphs, an experimental study // Experimental and efficient algorithms. Proc. 4th Int. Workshop WEA 2005 (Santorini Island, Greece, May 10–13, 2005). Heidelberg: Springer, 2005. P. 606–609. (Lect. Notes Comp. Sci.; V. 3503). DOI: 10.1007/11427186_54.
     
  8. Goodman A. W. On sets of acquaintances and strangers at any party // Am. Math. Mon. 1959. V. 66, No. 9. P. 778–783. DOI: 10.1080/00029890.1959.11989408.
     
  9. Sauvé L. On chromatic graphs // Am. Math. Mon. 1961. V. 68, No. 2. P. 107–111. DOI: 10.1080/00029890.1961.11989632.
     
  10. Pyatkin A. V., Lykhovyd E., Butenko S. I. The maximum number of induced open triangles in graphs of a given order // Optim. Lett. 2019. V. 13, No. 8. P. 1927–1935. DOI: 10.1007/s11590-018-1330-2.
     
  11. Пяткин А. В., Чёрных О. И. О максимальном числе открытых треугольников в графах с одинаковым числом вершин и рёбер // Дискрет. анализ и исслед. операций. 2022. Т. 29, № 1. С. 46–55.
     
  12. Пяткин А. В. О максимальном числе открытых треугольников в графах с малым числом рёбер // Дискрет. анализ и исслед. операций. 2024. Т. 31, № 3. С. 134–142.

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0019). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Пяткин Артём Валерьевич
  1. Институт математики им. С. Л. Соболева СО РАН, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: artem@math.nsc.ru

Статья поступила 19 марта 2025 г.
После доработки — 26 марта 2025 г.
Принята к публикации 22 апреля 2025 г.

Abstract:

In an undirected graph, a 3-vertex induced subgraph with exactly two edges is called an open triangle (OT). We consider the class of graphs in which the numbers of vertices and edges differ by a fixed constant c. The complete characterization of extremal OT graphs in this class with at least $c + 7$ vertices is obtained. 

Illustr. 1, bibliogr. 12.

References:
  1. E. C. Johnsen, Structure and process: Agreement models for friendship formation, Soc. Netw. 8 (3), 257–306 (1986).
     
  2. J. Moody, Matrix methods for calculating the triad census, Soc. Netw. 20 (4), 291–299 (1998).
     
  3. S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications (Camb. Univ. Press, Cambridge, 1994) (Struct. Anal. Soc. Sci., Vol. 8), DOI: 10.1017/cbo9780511815478.
     
  4. V. Batagelj and A. Mrvar, A subquadratic triad census algorithm for large sparse networks with small maximum degree, Soc. Netw. 23 (3), 237–243 (2001).
     
  5. R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, Network motifs: Simple building blocks of complex networks, Science 298, 824–827 (2002).
     
  6. G. Robins, A tutorial on methods for the modeling and analysis of social network data, J. Math. Psychol. 57, 261–274 (2013).
     
  7. T. Schank and D. Wagner, Finding, counting and listing all triangles in large graphs, an experimental study, in Experimental and Efficient Algorithms (Proc. 4th Int. Workshop WEA 2005, Santorini Island, Greece, May 10–13, 2005) (Springer, Heidelberg, 2005), pp. 606–609 (Lect. Notes Comp. Sci., Vol. 3503), DOI: 10.1007/11427186_54.
     
  8. A. W. Goodman, On sets of acquaintances and strangers at any party, Am. Math. Mon. 66 (9), 778–783 (1959), DOI: 10.1080/00029890.1959.11989408.
     
  9. L. Sauvé, On chromatic graphs, Am. Math. Mon. 68 (2), 107–111 (1961), DOI: 10.1080/00029890.1961.11989632.
     
  10. A. V. Pyatkin, E. Lykhovyd, and S. I. Butenko, The maximum number of induced open triangles in graphs of a given order, Optim. Lett. 13 (8), 1927–1935 (2019), DOI: 10.1007/s11590-018-1330-2.
     
  11. A. V. Pyatkin and O. I. Chernykh, On the maximum number of open triangles in graphs with the same number of vertices and edges, Diskretn. Anal. Issled. Oper. 29 (1), 46–55 (2022) [Russian] [J. Appl. Ind. Math. 16 (1), 116–121 (2022)].
     
  12. A. V. Pyatkin, On the maximum number of open triangles in graphs with few edges, Diskretn. Anal. Issled. Oper. 31 (3), 134–142 (2024) [Russian] [J. Appl. Ind. Math. 18 (3), 516–520 (2024)].