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

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

Пяткин А. В.
Дискретный анализ и исследование операций, 31, 3, 144–152 (2024)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2024.31.793

Аннотация:

Подмножество из трёх вершин, порождающее подграф ровно с двумя рёбрами, будем называть открытым треугольником (ОТ). Рассматривается задача поиска графов с максимальным числом ОТ. Доказано, что в классе графов, когда число рёбер превышает число вершин на фиксированную константу, такой граф единствен при достаточно большом числе вершин. 
Библиогр. 11.

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

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

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

E-mail: artem@math.nsc.ru

Статья поступила 25 января 2024 г.
После доработки — 20 февраля 2024 г.
Принята к публикации 22 марта 2024 г.

Abstract:

A three-vertex subset is called an open triangle (OT) if it induces a subgraph with exactly two edges. The problem of finding graphs with maximum number of OTs is considered. It is proved that, in case of sufficiently many vertices, such a graph is unique in the class of graphs with constant difference between the numbers of edges and vertices. 
Bibliogr. 11.

References:
  1. E. C. Johnsen, Structure and process: Agreement models for friendship formation, Social Networks 8, 257–306 (1986).
     
  2. S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications (Camb. Univ. Press, Cambridge, UK, 1994), DOI: 10.1017/ cbo9780511815478.
     
  3. J. Moody, Matrix methods for calculating the triad census, Social Networks 20, 291–299 (1998).
     
  4. G. Robins, A tutorial on methods for the modeling and analysis of social network data, J. Math. Psychol. 57, 261–274 (2013).
     
  5. 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, Santorini Island, Greece, May 10–13, 2005) (Springer, Heidelberg, 2005), pp. 606–609 (Lect. Notes Comput. Sci., Vol. 3503), DOI: 10.1007/11427186_54.
     
  6. 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).
     
  7. 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.
     
  8. L. Sauve, On chromatic graphs, Am. Math. Mon. 68 (2), 107–111 (1961), DOI: 10.1080/00029890.1961.11989632.
     
  9. A. Pyatkin, E. Lykhovyd, and S. Butenko, The maximum number of induced open triangles in graphs of a given order, Optim. Lett. 13 (8), 1927–1935 (2018), DOI: 10.1007/s11590-018-1330-2.
     
  10. 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)].
     
  11. V. Batagelj and A. Mrvar, A subquadratic triad census algorithm for large sparse networks with small maximum degree, Soc. Networks 23, 237–243 (2001).