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.
@article{722,
title = {The number of edges of the edge polytope of a finite simple graph},
journal = {ARS MATHEMATICA CONTEMPORANEA},
volume = {12},
year = {2016},
doi = {10.26493/1855-3974.722.bba},
language = {EN},
url = {http://dml.mathdoc.fr/item/722}
}
Hibi, Takayuki; Mori, Aki; Ohsugi, Hidefumi; Shikama, Akihiro. The number of edges of the edge polytope of a finite simple graph. ARS MATHEMATICA CONTEMPORANEA, Tome 12 (2016) . doi : 10.26493/1855-3974.722.bba. http://gdmltest.u-ga.fr/item/722/