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)

This article is cited in 1 paper

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, 2025