Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 29, No 1, 2022, P. 46-55
UDC 519.17
A. V. Pyatkin and O. I. Chernykh
On the maximum number of open triangles in graphs with the same number of vertices and edge
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.
Keywords: open triangles, induced subgraphs, unicyclic graphs.
DOI: 10.33048/daio.2022.29.723
Artem V. Pyatkin 1,2
Oksana I. Chernykh 2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: artem@math.nsc.ru, o.chernykh@g.nsu.ru
Received July 26, 2021
Revised September 27, 2021
Accepted September 28, 2021
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).
