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

Artem Pyatkin, Eugene Lykhovyd, Sergiy Butenko

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Pages (from-to)1927-1935
Number of pages9
JournalOptimization Letters
Volume13
Issue number8
DOIs
Publication statusPublished - 1 Nov 2019

Keywords

  • Induced 3-paths
  • Induced open triangles
  • Network analysis

Fingerprint

Dive into the research topics of 'The maximum number of induced open triangles in graphs of a given order'. Together they form a unique fingerprint.

Cite this