On complete multipartite derangement graphs

angleški

2021

letnik 21, številka 1

Cayleyjevi grafi   Erdős-Ko-Rado izrek   koklike   premestitveni graf

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

Če je dana končna tranzitivna permutacijska grupa ?$G \leq \mathrm{Sym}( \Omega )$?, in je ?$| \Omega| \geq 2$?, potem je premestitveni graf ?$\Gamma_G$? grafa ?$G$? Cayleyev graf ?$\mathrm{Cay} (G, \mathrm{Der}(G))$?, pri čemer je ?$\mathrm{Der}(G)$? množica vseh premestitev grafa ?$G$?. Meagher in dr. On triangles in derangement graphs, J. Combin. Theory Ser. A, 180:105390, 2021 so pred kratkim dokazali, da je ?$\mathrm{Sym}(2)$?, delujoča na ?$\{1, 2\}$?, edina tranzitivna grupa, katere premestitveni graf je dvodelen, vsaka tranzitivna grupa stopnje najmanj tri pa ima trikotnik v svojem premestitvenem grafu. Pokazali so tudi, da obstajajo tranzitivne grupe, katerih premestitveni grafi so polni večdelni. V članku predstavimo dve novi družini tranzitivnih grup s polnimi večdelnimi premestitvenimi grafi. Dokažemo tudi, da če je ?$p$? liho praštevilo, ?$G$? pa tranzitivna grupa stopnje ?$2p$?, potem je neodvisnostno število grafa ?$\Gamma_G$? največ dvakratnik velikosti točkovnega stabilizatorja grafa ?$G$?.

22.11.2022