262 KB25 KB200820252015Alspach, BrianDobson, Edwardštevilka:1letnik:8str. 215-223COBISSID:17371225ISSN:1855-3966URN:URN:NBN:SI:doc-BJRX7J58enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaautomorphism groupCayley graphCayleyjev grafgrupa avtomorfizmovHamiltonianHamiltonov grafprisekanjeskoraj-uniformne družine delnih vsottruncationOn automorphism groups of graph truncations|It is well known that the Petersen graph, the Coxeter graph, as well as the graphs obtained from these two graphs by replacing each vertex with a triangle, are trivalent vertex-transitive graphs without Hamilton cycles, and are indeed the only known connected vertex-transitive graphs of valency at least two without Hamilton cycles. It is known by many that the replacement of a vertex with a triangle in a trivalent vertex-transitive graph results in a vertex-transitive graph if and only if the original graph is also arc-transitive. In this paper, we generalize this notion to ?$t$?-regular graphs ?$\Gamma$? and replace each vertex with a complete graph ?$K_t$? on ?$t$? vertices. We determine necessary and sufficient conditions for ?$\mathscr{T}(\Gamma)$? to be hamiltonian, show ?$\text{Aut}(\mathscr{T}(\Gamma)) \cong \text{Aut}(\Gamma)$?, as well as show that if ?$\Gamma$? is vertex-transitive, then ?$\mathscr{T}(\Gamma)$? is vertex-transitive if and only if ?$\Gamma$? is arc-transitive. Finally, in the case where ?$t$? is prime we determine necessary and sufficient conditions for ?$\mathscr{T}(\Gamma)$? to be isomorphic to a Cayley graph as well as an additional necessary and sufficient condition for ?$\mathscr{T}(\Gamma)$? to be vertex-transitiveZnano 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-tranzitivenTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije