The maximum number of induced open triangles in graphs of a given order
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
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.