The maximum number of induced open triangles in graphs of a given order
- Additional Document Info
- View All
© 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)⌊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.
author list (cited authors)
Pyatkin, A., Lykhovyd, E., & Butenko, S.