Standard

The maximum number of induced open triangles in graphs of a given order. / Pyatkin, Artem; Lykhovyd, Eugene; Butenko, Sergiy.

In: Optimization Letters, Vol. 13, No. 8, 01.11.2019, p. 1927-1935.

Research output: Contribution to journal › Article › peer-review

Harvard

Pyatkin, A, Lykhovyd, E & Butenko, S 2019, 'The maximum number of induced open triangles in graphs of a given order', Optimization Letters, vol. 13, no. 8, pp. 1927-1935. https://doi.org/10.1007/s11590-018-1330-2

APA

Pyatkin, A., Lykhovyd, E., & Butenko, S. (2019). The maximum number of induced open triangles in graphs of a given order. Optimization Letters, 13(8), 1927-1935. https://doi.org/10.1007/s11590-018-1330-2

Vancouver

Pyatkin A, Lykhovyd E, Butenko S. The maximum number of induced open triangles in graphs of a given order. Optimization Letters. 2019 Nov 1;13(8):1927-1935. doi: 10.1007/s11590-018-1330-2

Author

Pyatkin, Artem ; Lykhovyd, Eugene ; Butenko, Sergiy. / The maximum number of induced open triangles in graphs of a given order. In: Optimization Letters. 2019 ; Vol. 13, No. 8. pp. 1927-1935.

BibTeX

@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",

}

RIS

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 -

ID: 17250117