623 KB29 KB200820252022Jorgensen, Leif K.Pineda-Villavicencio, GuillermoUgon, Julienštevilka:2letnik:22P2.09 (10 str.)DOI:10.26493/1855-3974.2577.25dCOBISSID_HOST:117087235ISSN:1855-3966URN:URN:NBN:SI:doc-GDLZJWSVenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaCartesian productciklični politopconnectivitycyclic polytopedual polytopedualni politopkartezični produktk-linkedk-vezanlinkednesspovezljivostvezanostLinkedness of Cartesian products of complete graphs|This paper is concerned with the linkedness of Cartesian products of complete graphs. A graph with at least ?$2k$? vertices is ?$k$?-linked if, for every set of ?$2k$? distinct vertices organised in arbitrary ?$k$? pairs of vertices, there are ?$k$? vertex-disjoint paths joining the vertices in the pairs. We show that the Cartesian product ?$K^{d_1+1} \times K^{d_2+1}$? of complete graphs ?$K^{d_1+1}$? and ?$K^{d_2+1}$? is ?$\lfloor (d_1 + d_2)/2 \rfloor $?-linked for ?$d_1, d_2 \geq 2$?, and this is best possible. This result is connected to graphs of simple polytopes. The Cartesian product ?$K^{d_1+1} \times K^{d_2+1}$? is the graph of the Cartesian product ?$T(d_1) \times T(d_2)$? of a ?$d_1$?-dimensional simplex ?$T(d_1)$? and a ?$d_2$?-dimensional simplex ?$T(d_2)$?. And the polytope ?$T(d_1) \times T(d_2)$? is a simple polytope, a ?$(d_1 + d_2)$?-dimensional polytope in which every vertex is incident to exactly ?$d_1 + d_2$? edges. While not every ?$d$?-polytope is ?$\lfloor d/2 \rfloor $?-linked, it may be conjectured that every simple ?$d$?-polytope is. Our result implies the veracity of the revised conjecture for Cartesian products of two simplicesTa članek obravnava veznost kartezičnega produkta polnih grafov. Graf z najmanj ?$2k$? vozlišči je ?$k$?-vezan, če za vsako množico ?$2k$? različnih vozlišč, razvrščenih v poljubne ?$k$? pare, obstaja ?$k$? vozliščno disjunktnih poti, ki ta vozlišča povezujejo v pare. Dokažemo, da je kartezični produkt ?$K^{d_1+1} \times K^{d_2+1}$? polnih grafov ?$K^{d_1+1}$ in $K^{d_2+1}$? ?$\lfloor (d_1 + d_2)/2 \rfloor $?-vezan za ?$d_1, d_2 \geq 2$?, in da je to najboljši možni rezultat. Ta razultat je povezan z grafi enostavnih politopov. Kartezični produkt ?$K^{d_1+1} \times K^{d_2+1}$? je graf kartezičnega produkta ?$T(d_1) \times T(d_2)$?-dimenzionalnega simpleksa ?T$d_1$? ter ?$d_2$?-dimenzionalnega simpleksa ?$T(d_2)$?. Politop ?$T(d_1) \times T(d_2)$? pa je enostaven politop, ?$(d_1 + d_2)$?-dimenzionalen politop, v katerem je vsaka točka incidentna natančno ?$d_1 + d_2$? povezavam. Čeprav ni vsak ?$d$?-politop ?$\lfloor d/2 \rfloor $?-vezan, pa lahko domnevamo, da vsak enostaven ?$d$?-politop to je. Naš rezultat implicira resničnost revidirane domneve za kartezične produkte dveh simpleksovTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije