On automorphism groups of graph truncations

angleški

2015

letnik 8, številka 1

Cayleyjev graf   grupa avtomorfizmov   Hamiltonov graf   prisekanje   skoraj-uniformne družine delnih vsot

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

Znano je, da so Petersenov graf, Coxeterjev graf, pa tudi grafi, dobljeni iz njiju z nadomestitvijo vsakega vozlišča s trikotnikom, trivalentni vozliščno-tranzitivni grafi brez Hamiltonovih ciklov; to so tudi edini znani povezani vozlično-tranzitivni grafi valence najmanj dve brez Hamiltonovih ciklov. Znano je tudi, da zamenjava vozlišča s trikotnikom v trivalentnem vozliščno-tranzitivnem grafu da vozliščno-tranzitiven graf če in samo če je prvotni graf tudi ločno-tranzitiven. V tem članku posplošimo ta koncept na ?$t$?-regularne grafe ?$\Gamma$? in nadomestimo vsako vozlišče s polnim grafom ?$K_t$? na ?$t$? vozliščih. Določimo potrebne in zadostne pogoje za to, da je ?$\mathscr{T}(\Gamma)$? hamiltonski, pokažemo, da je ?$\text{Aut}(\mathscr{T}(\Gamma)) \cong \text{Aut}(\Gamma)$?, pokažemo pa tudi, da če je ?$\Gamma$? vozliščno-tranzitiven, potem je ?$\mathscr{T}(\Gamma)$? vozliščno-tranzitiven, če in samo če je ?$\Gamma$? ločno-tranzitiven. V primeru, ko je ?$t$? praštevilo, določimo potrebne in zadostne pogoje za to, da je ?$\mathscr{T}(\Gamma)$? izomorfen Cayleyevemu grafu, pa tudi dodaten potreben in zadosten pogoj za to, da je ?$\mathscr{T}(\Gamma)$? vozliščno-tranzitiven.

29.05.2020