Naj bo ?$d \ge 3$? celo število. Znano je, da je število povezav povezavnega politopa polnega grafa z ?$d$? vozlišči enako ?$d(d-1)(d-2)/2$?. V tem članku študiramo največje možno število ?$\mu_{d}$? povezav, ki jih lahko imajo povezavni politopi, dobljeni iz končnih enostavnih grafov z ?$d$? vozlišči. Pokažemo, da je ?$\mu_{d} = d(d-1)(d-2)/2$? če in samo če ?$3 \leq d \leq 14$?. Poleg tega študiramo asimptotično vedenje števila ?$\mu_{d}$?. Tran-Ziegler sta dobila spodnjo mejo za ?$\mu_{d}$? tako, da sta konstruirala slučajni graf. Uspelo nam je izboljšati to mejo s konstruiranjem ne-slučajnega grafa in slučajnega grafa, katerega komplement je dvodelen.

Pravice

URN

URN:NBN:SI:DOC-U6VQ2HHQ

COBISSID

17833561

Objavljeno

29.05.2020

Metapodatki

Citiranje

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, letnik 10, številka 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 letnik 10. številka 2 (2016) str. 323-332.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-U6VQ2HHQ>

Ars mathematica contemporanea
2008-
(Zbirni zapis)