Geodesic
On the maximum number of open triangles in graphs with few edges
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 3, pp. 144-152 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: open triangle, induced subgraph, sparse graph. 
@article{DA_2024_31_3_a6,
     author = {A. V. Pyatkin},
     title = {On the maximum number of open triangles in~graphs with few edges},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {144--152},
     year = {2024},
     volume = {31},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_3_a6/}
}
TY  - JOUR
AU  - A. V. Pyatkin
TI  - On the maximum number of open triangles in graphs with few edges
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 144
EP  - 152
VL  - 31
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_3_a6/
LA  - ru
ID  - DA_2024_31_3_a6
ER  - 
%0 Journal Article
%A A. V. Pyatkin
%T On the maximum number of open triangles in graphs with few edges
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 144-152
%V 31
%N 3
%U http://geodesic.mathdoc.fr/item/DA_2024_31_3_a6/
%G ru
%F DA_2024_31_3_a6
A. V. Pyatkin. On the maximum number of open triangles in graphs with few edges. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 3, pp. 144-152. http://geodesic.mathdoc.fr/item/DA_2024_31_3_a6/

[1] E. C. Johnsen, “Structure and process: Agreement models for friendship formation”, Social Networks, 8 (1986), 257–306 | DOI

[2] S. Wasserman, K. Faust, Social network analysis: Methods and applications, Camb. Univ. Press, Cambridge, UK, 1994, 852 pp. | DOI

[3] Moody J., “Matrix methods for calculating the triad census”, Social Networks, 20 (1998), 291–299 | DOI

[4] G. Robins, “A tutorial on methods for the modeling and analysis of social network data”, J. Math. Psychol., 57 (2013), 261–274 | DOI

[5] T. Schank, 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), Lect. Notes Comput. Sci., 3503, Springer, Heidelberg, 2005, 606–609 | DOI

[6] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, U. Alon, “Network motifs: Simple building blocks of complex networks”, Science, 298 (2002), 824–827 | DOI

[7] A. W. Goodman, “On sets of acquaintances and strangers at any party”, Am. Math. Mon., 66:9 (1959), 778–783 | DOI

[8] Sauve L., “On chromatic graphs”, Am. Math. Mon., 68:2 (1961), 107–111 | DOI

[9] A. Pyatkin, E. Lykhovyd, S. Butenko, “The maximum number of induced open triangles in graphs of a given order”, Optim. Lett., 13:8 (2018), 1927–1935 | DOI

[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”, J. Appl. Ind. Math., 16:1 (2022), 116–121 | DOI

[11] V. Batagelj, A. Mrvar, “A subquadratic triad census algorithm for large sparse networks with small maximum degree”, Soc. Networks, 23 (2001), 237–243 | DOI