RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2022 Volume 29, Issue 1, Pages 46–55 (Mi da1292)

On the maximum number of open triangles in graphs with the same number of vertices and edges

A. V. Pyatkinab, O. I. Chernykhb

a Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, 630090 Novosibirsk, Russia
b Novosibirsk State University, 2 Pirogov Street, 630090 Novosibirsk, Russia

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.

UDC: 519.17

Received: 26.07.2021
Revised: 27.09.2021
Accepted: 28.09.2021

DOI: 10.33048/daio.2022.29.723



© Steklov Math. Inst. of RAS, 2024