Geodesic
The number of edges of the edge polytope of a finite simple graph
Ars Mathematica Contemporanea, Tome 10 (2016) no. 2, pp. 323-332.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.722.bba
Keywords: Finite simple graph, edge polytope 
@article{10_26493_1855_3974_722_bba,
     author = {Takayuki Hibi and Aki Mori and Hidefumi Ohsugi and Akihiro Shikama},
     title = {The number of edges of the edge polytope of a finite simple graph},
     journal = {Ars Mathematica Contemporanea},
     pages = {323--332},
     publisher = {mathdoc},
     volume = {10},
     number = {2},
     year = {2016},
     doi = {10.26493/1855-3974.722.bba},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.722.bba/}
}
TY  - JOUR
AU  - Takayuki Hibi
AU  - Aki Mori
AU  - Hidefumi Ohsugi
AU  - Akihiro Shikama
TI  - The number of edges of the edge polytope of a finite simple graph
JO  - Ars Mathematica Contemporanea
PY  - 2016
SP  - 323
EP  - 332
VL  - 10
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.722.bba/
DO  - 10.26493/1855-3974.722.bba
LA  - en
ID  - 10_26493_1855_3974_722_bba
ER  - 
%0 Journal Article
%A Takayuki Hibi
%A Aki Mori
%A Hidefumi Ohsugi
%A Akihiro Shikama
%T The number of edges of the edge polytope of a finite simple graph
%J Ars Mathematica Contemporanea
%D 2016
%P 323-332
%V 10
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.722.bba/
%R 10.26493/1855-3974.722.bba
%G en
%F 10_26493_1855_3974_722_bba
Takayuki Hibi; Aki Mori; Hidefumi Ohsugi; Akihiro Shikama. The number of edges of the edge polytope of a finite simple graph. Ars Mathematica Contemporanea, Tome 10 (2016) no. 2, pp. 323-332. doi : 10.26493/1855-3974.722.bba. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.722.bba/

Cité par Sources :