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

Artem Pyatkin, Eugene Lykhovyd, Sergiy Butenko

Результат исследования: Научные публикации в периодических изданияхстатья

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)1927-1935
Число страниц9
ЖурналOptimization Letters
Том13
Номер выпуска8
DOI
СостояниеОпубликовано - 1 ноя 2019

    Fingerprint

Цитировать