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

Diskretn. Anal. Issled. Oper., 2024 Volume 31, Issue 3, Pages 144–152 (Mi da1357)

On the maximum number of open triangles in graphs with few edges

A. V. Pyatkin

Sobolev Institute of Mathematics, 4 Koptyug Avenue, 630090 Novosibirsk, Russia

Abstract: 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.

UDC: 519.17

Received: 25.01.2024
Revised: 20.02.2024
Accepted: 22.03.2024

DOI: 10.33048/daio.2024.31.793


 English version:
Journal of Applied and Industrial Mathematics, 2024, 18:3, 516–520


© Steklov Math. Inst. of RAS, 2025