TY - JOUR

T1 - The maximum number of induced open triangles in graphs of a given order

AU - Pyatkin, Artem

AU - Lykhovyd, Eugene

AU - Butenko, Sergiy

PY - 2019/11/1

Y1 - 2019/11/1

N2 - An open triangle is a simple, undirected graph consisting of three vertices and two edges. It is shown that the maximum number of induced open triangles in a graph on n vertices is given by (n2-1)⌊n2⌋⌈n2⌉. The maximum is achieved for the complete bipartite graph K⌊ n / 2 ⌋ , ⌈ n / 2 ⌉. The maximum expected number of open triangles in a uniform random graph on n vertices is observed to be asymptotically equivalent.

AB - An open triangle is a simple, undirected graph consisting of three vertices and two edges. It is shown that the maximum number of induced open triangles in a graph on n vertices is given by (n2-1)⌊n2⌋⌈n2⌉. The maximum is achieved for the complete bipartite graph K⌊ n / 2 ⌋ , ⌈ n / 2 ⌉. The maximum expected number of open triangles in a uniform random graph on n vertices is observed to be asymptotically equivalent.

KW - Induced 3-paths

KW - Induced open triangles

KW - Network analysis

UR - http://www.scopus.com/inward/record.url?scp=85051467750&partnerID=8YFLogxK

U2 - 10.1007/s11590-018-1330-2

DO - 10.1007/s11590-018-1330-2

M3 - Article

AN - SCOPUS:85051467750

VL - 13

SP - 1927

EP - 1935

JO - Optimization Letters

JF - Optimization Letters

SN - 1862-4472

IS - 8

ER -