Geodesic
On the maximum number of open triangles in graphs with the same number of vertices and edges
Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 46-55 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{DA_2022_29_1_a3,
     author = {A. V. Pyatkin and O. I. Chernykh},
     title = {On the maximum number of open triangles in~graphs with the same number of~vertices~and~edges},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {46--55},
     year = {2022},
     volume = {29},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2022_29_1_a3/}
}
TY  - JOUR
AU  - A. V. Pyatkin
AU  - O. I. Chernykh
TI  - On the maximum number of open triangles in graphs with the same number of vertices and edges
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2022
SP  - 46
EP  - 55
VL  - 29
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DA_2022_29_1_a3/
LA  - ru
ID  - DA_2022_29_1_a3
ER  - 
%0 Journal Article
%A A. V. Pyatkin
%A O. I. Chernykh
%T On the maximum number of open triangles in graphs with the same number of vertices and edges
%J Diskretnyj analiz i issledovanie operacij
%D 2022
%P 46-55
%V 29
%N 1
%U http://geodesic.mathdoc.fr/item/DA_2022_29_1_a3/
%G ru
%F DA_2022_29_1_a3
A. V. Pyatkin; O. I. Chernykh. On the maximum number of open triangles in graphs with the same number of vertices and edges. Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 46-55. http://geodesic.mathdoc.fr/item/DA_2022_29_1_a3/

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

[2] Robins G., “A tutorial on methods for the modeling and analysis of social network data”, J. Math. Psychol., 57 (2013), 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), Lect. Notes Comput. Sci., 3503, Springer, Heidelberg, 2005, 606–609

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

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

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

[7] Wasserman S., Faust K., Social network analysis: Methods and applications, Camb. Univ. Press, New York, 1994

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

[9] Sauvé L., “On chromatic graphs”, Amer. Math. Mon., 68:2 (1961), 107–111

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