The number of edges of the edge polytope of a finite simple graph

Abstract

Let d ≥ 3 be an integer. It is known that the number of edges of the edge polytope of the complete graph with d vertices is d(d − 1)(d − 2) / 2. In this paper, we study the maximum possible number μd of edges of the edge polytope arising from finite simple graphs with d vertices. We show that μd = d(d − 1)(d − 2) / 2 if and only if 3 ≤ d ≤ 14. In addition, we study the asymptotic behavior of μd. Tran–Ziegler gave a lower bound for μd by constructing a random graph. We succeeded in improving this bound by constructing both a non-random graph and a random graph whose complement is bipartite.

Locations

• arXiv (Cornell University) - View - PDF
• DataCite API - View
• Ars Mathematica Contemporanea - View - PDF