330 KB20 KB200820252016Hibi, TakayukiMori, AkiOhsugi, HidefumiShikama, Akihiroletnik:10številka:2str. 323-332COBISSID:17833561ISSN:1855-3966URN:URN:NBN:SI:doc-U6VQ2HHQenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaedge polytopefinite simple graphkončni enostavni grafpovezavni politopThe number of edges of the edge polytope of a finite simple graph|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 bipartiteNaj 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 dvodelenTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije