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

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

Пяткин А. В., Черных О. И.
Дискретный анализ и исследование операций, 29, 1, 46-55 (2022)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2022.29.723

Аннотация:

Открытым треугольником (ОТ) называется трёхвершинный подграф с двумя рёбрами, т. е. индуцированный путь длины 2. В работе получена формула для максимально возможного числа ОТ в $n$-вершинных графах c $n$ рёбрами и дана полная характеризация графов, на которых достигается этот максимум. 
Ил. 2, библиогр. 10.

Литература:
  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 // 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).
     
  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: Methods and applications. New York: Camb. Univ. Press, 1994. 
     
  8. Goodman A. W. On sets of acquaintances and strangers at any party // Amer. Math. Mon. 1959. V. 66, No. 9. P. 778–783.
     
  9. Sauvé L. On chromatic graphs // Amer. Math. Mon. 1961. V. 68, No. 2. 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.

Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований (проект № 20–01–00045).

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

E-mail: artem@math.nsc.ru

Черных Оксана Ильинична
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: o.chernykh@g.nsu.ru

Статья поступила 26 июля 2021 г. 
После доработки — 27 сентября 2021 г. 
Принята к публикации 28 сентября 2021 г.

Abstract:

An open triangle (OT) is a 3-vertex subgraph with two edges, i. e. an induced path of length 2. A formula for the maximum number of OT in $n$-vertex graphs with $n$ edges is proved in the paper. We also present a full characterization of graphs for which the maximum is attained. 
Illustr. 2, bibliogr. 10.

References:
  1. 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).
     
  2. G. Robins, A tutorial on methods for the modeling and analysis of social network data, J. Math. Psychol. 57, 261–274 (2013).
     
  3. T. Schank and D. Wagner, 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) (Springer, Heidelberg, 2005), pp. 606–609 (Lect. Notes Comput. Sci., Vol. 3503).
     
  4. V. Batagelj and A. Mrvar, A subquadratic triad census algorithm for large sparse networks with small maximum degree, Soc. Networks 23, 237–243 (2001).
     
  5. E. C. Johnsen, Structure and process: agreement models for friendship formation, Soc. Networks 8, 257–306 (1986).
     
  6. J. Moody, Matrix methods for calculating the triad census, Soc. Networks 20, 291–299 (1998).
     
  7. S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications (Camb. Univ. Press, New York, 1994).
     
  8. A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Mon. 66 (9), 778–783 (1959).
     
  9. L. Sauvé, On chromatic graphs, Amer. Math. Mon. 68 (2), 107–111 (1961).
     
  10. 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).