On graphs with small number of edges having extremal number of open triangles

A. V. Pyatkin

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

Abstract: In an undirected graph, a $3$-vertex induced subgraph with exactly two edges is called an open triangle (OT). We consider the class of graphs in which the numbers of vertices and edges differ by a fixed constant $c.$ The complete characterization of extremal OT graphs in this class with at least $c+7$ vertices is obtained. Illustr. 1, bibliogr. 12.

Keywords: open triangle, induced subgraph, sparse graph.

UDC: 519.17

Received: 19.03.2025
Revised: 26.03.2025
Accepted: 22.04.2025

DOI: 10.33048/daio.2025.32.830