406 KB39 KB200820252021Razafimahatratra, Andriaherimanana Sarobidyštevilka:1letnik:21str. 89-103DOI:10.26493/1855-3974.2554.856COBISSID_HOST:111650563ISSN:1855-3966URN:URN:NBN:SI:doc-8A8H3TZJenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaCayley graphsCayleyjevi graficocliquesderangement graphErdős-Ko-Rado izrekErdős-Ko-Rado theoremkoklikepremestitveni grafOn complete multipartite derangement graphs|Given a finite transitive permutation group ?$G \leq \mathrm{Sym}( \Omega )$?, with ?$| \Omega| \geq 2$?, the derangement graph $?\Gamma_G$? of ?$G$? is the Cayley graph ?$\mathrm{Cay} (G, \mathrm{Der}(G))$?, where ?$\mathrm{Der}(G)$? is the set of all derangements of ?$G$?. K. Meagher et al. J. Comb. Theory, Ser. A 180, Article ID 105390, 27 p. (2021) recently proved that ?$\mathrm{Sym}(2)$? acting on ?$\{1, 2\}$? is the only transitive group whose derangement graph is bipartite and any transitive group of degree at least three has a triangle in its derangement graph. They also showed that there exist transitive groups whose derangement graphs are complete multipartite. This paper gves two new families of transitive groups with complete multipartite derangement graphs. In addition, we prove that if ?$p$? is an odd prime and ?$G$? is a transitive group of degree ?$2p$?, then the independence number of ?$\Gamma_G$? is at most twice the size of a point-stabilizer of ?$G$?Č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$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije