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

abstract

• 2018, Springer-Verlag GmbH Germany, part of Springer Nature. 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)n2n2. The maximum is achieved for the complete bipartite graph Kn/2,n/2. The maximum expected number of open triangles in a uniform random graph on n vertices is observed to be asymptotically equivalent.

authors

• Butenko, Sergiy

published proceedings

• OPTIMIZATION LETTERS

author list (cited authors)

• Pyatkin, A., Lykhovyd, E., & Butenko, S.

citation count

• 5

complete list of authors

• Pyatkin, Artem||Lykhovyd, Eugene||Butenko, Sergiy

publication date

• November 2019

publisher

• Springer Nature  Publisher

published in

• Optimization Letters  Journal

keywords

• Induced 3-paths
• Induced Open Triangles
• Network Analysis

Digital Object Identifier (DOI)

• 10.1007/s11590-018-1330-2

start page

• 1927

end page

• 1935

volume

• 13

issue

• 8

URL

• http://dx.doi.org/10.1007/s11590-018-1330-2