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

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)⌊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.

citation count

  • 2

publication date

  • October 2018