Let ?$d \ge 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 ?$\mu_{d}$? of edges of the edge polytope arising from finite simple graphs with ?$d$? vertices. We show that ?$\mu_{d} = d(d-1)(d-2)/2$? if and only if ?$3 \leq d \leq 14$?. In addition, we study the asymptotic behavior of ?$\mu_{d}$?. Tran-Ziegler gave a lower bound for ?$\mu_{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.

Rights

URN

URN:NBN:SI:DOC-U6VQ2HHQ

COBISSID

17833561

Added

29.05.2020

Metadata

Citation

APA:

Hibi, Takayuki, Mori, Aki, Ohsugi, Hidefumi, Shikama, Akihiro (2016). The number of edges of the edge polytope of a finite simple graph. Ars mathematica contemporanea, volume 10, issue 2, str. 323-332. URN:NBN:SI:DOC-U6VQ2HHQ from http://www.dlib.si

MLA:

Hibi, Takayuki, Mori, Aki, Ohsugi, Hidefumi, Shikama, Akihiro. "The number of edges of the edge polytope of a finite simple graph." Ars mathematica contemporanea volume 10. issue 2 (2016) str. 323-332.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-U6VQ2HHQ>

Ars mathematica contemporanea
2008-
(Assembly record)