Linkedness of Cartesian products of complete graphs

angleški

2022

letnik 22, številka 2

ciklični politop   dualni politop   kartezični produkt   k-vezan   povezljivost   vezanost

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Ta č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 simpleksov.

22.11.2022