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

Artem Pyatkin; Eugene Lykhovyd; Sergiy Butenko

doi:10.1007/s11590-018-1330-2

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 _/ ₂ _⌋ _, _⌈ _n _/ ₂ _⌉. 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	https://doi.org/10.1007/s11590-018-1330-2
Состояние	Опубликовано - 1 ноя 2019

Доступ к документу

10.1007/s11590-018-1330-2

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «The maximum number of induced open triangles in graphs of a given order». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

@article{44e0b52fb40c44c1bebaaa8699ddd7e8,

title = "The maximum number of induced open triangles in graphs of a given order",

abstract = "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.",

keywords = "Induced 3-paths, Induced open triangles, Network analysis",

author = "Artem Pyatkin and Eugene Lykhovyd and Sergiy Butenko",

year = "2019",

month = nov,

day = "1",

doi = "10.1007/s11590-018-1330-2",

language = "English",

volume = "13",

pages = "1927--1935",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "8",

}

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 -