On generalized truncations of complete graphs

angleški

2020

letnik 19, številka 2

Cayleyjev graf   grupa avtomorfizmov   prisekanje   vozliščna tranzitivnost

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

Za ?$k$?-regularni graf ?$\Gamma$? in za graf ?$\Upsilon$? reda ?$k$? definiramo posplošeno prisekanje grafa ?$\Gamma$? z grafom ?$\Upsilon$?, tako da vsako vozlišče grafa ?$\Gamma$? nadomestimo s kopijo grafa ?$\Upsilon$?. E. Eiben, R. Jajcay in P. Šparl so vpeljali metodo za konstruiranje vozliščno tranzitivnih posplošenih prisekanj. Za potrebe tega članka imenujemo grafe, ki jih dobimo z metodo Eibena et al., posebna posplošena prisekanja. V svojem članku so Eiben et al. postavili problem klasifikacije posebnih posplošenih prisekanj polnega grafa ?$K_n$? s ciklom reda ?$n-1$?. V tem prispevku popolnoma rešimo njihov problem, tako da dokažemo, da je z izjemo ?$n=6$?, vsako posebno prisekanje grafa ?$K_n$? s ciklom reda ?$n-1$? Cayleyjev graf grupe AGL?$(1, n)$?, kjer je ?$n$? potenca praštevila. Poleg tega določimo za vsakega od teh grafov njegovo grupo avtomorfizmov in tudi izomorfizme med njimi.

28.04.2021