21. Semiregular automorphisms of vertex-transitive graphs of certain valenciesEdward Dobson, Aleksander Malnič, Dragan Marušič, Lewis A. Nowitz, 2007, original scientific article Abstract: It is shown that a vertex-transitive graph of valency ▫$p+1$▫, ▫$p$▫ a prime, admitting a transitive action of a ▫$\{2,p\}$▫-group, has a non-identity semiregular automorphism. As a consequence, it is proved that a quartic vertex-transitive graph has a non-identity semiregular automorphism, thus giving a partial affirmative answer to the conjecture that all vertex-transitive graphs have such an automorphism and, more generally, that all 2-closed transitive permutation groups contain such an element (see [D. Marušic, On vertex symmetric digraphs, Discrete Math. 36 (1981) 69-81; P.J. Cameron (Ed.), Problems from the Fifteenth British Combinatorial Conference, Discrete Math. 167/168 (1997) 605-615]).
Keywords: mathematics, graph theory, transitive permutation group, 2-closed group, semiregular automorphism, vertex-transitive graph
Published in RUP: 03.04.2017; Views: 2494; Downloads: 83
 Link to full text |
22. |
23. |
24. Določeni razredi (hiper)grafov in njihove algebraične lastnosti : doktorska disertacijaPaweł Petecki, 2016, doctoral dissertation Keywords: hypergraph, hamiltonian cycle, decomposition, double generalized Petersen graph, automorphism group, vertex-transitive, sign graph, L-eigenvalue, lollipop graph
Published in RUP: 09.08.2016; Views: 3189; Downloads: 30
Link to full text |
25. |
26. Algebraični aspekti teorije grafov : doktorska disertacijaAdemir Hujdurović, 2013, doctoral dissertation Keywords: circulant, bicirculant, semiregular automorphism, vertex-transitive graph, half-arc-transitive graph, snark, Cayley graph, quasi m-Cayley graph, generalized Cayley graph, I-regular action, regular cover of a graph, automorphism group
Published in RUP: 10.07.2015; Views: 3495; Downloads: 42
Link to full text |
27. Distance-regular Cayley graphs on dihedral groupsŠtefko Miklavič, Primož Potočnik, 2005, original scientific article Abstract: The main result of this article is a classification of distance-regular Cayley graphs on dihedral groups. There exist four obvious families of such graphs, which are called trivial. These are: complete graphs, complete bipartite graphs, complete bipartite graphs with the edges of a 1-factor removed, and cycles. It is proved that every non-trivial distance-regular Cayley graph on a dihedral group is bipartite, non-antipodal, has diameter 3 and arises either from a cyclic di#erence set, or possibly (if any such exists) from a dihedral difference set satisfying some additional conditions. Finally, all distance-transitive Cayley graphs on dihedral groups are determined. It transpires that a Cayley graph on a dihedral group is distance-transitive if and only if it is trivial, or isomorphic to the incidence or to the non-incidence graph of a projective space ▫$\mathrm{PG}_{d-1} (d,q)$▫, ▫$d \ge 2$▫, or the unique pair of complementary symmetric designs on 11 vertices.
Keywords: mathematics, grah theory, distance-regular graph, distance-transitive graph, Cayley graph, dihedral group, dihedrant, difference set
Published in RUP: 10.07.2015; Views: 2610; Downloads: 90
Link to full text |
28. |
29. |
30. Hamilton cycles in (2, odd, 3)-Cayley graphsHenry Glover, Klavdija Kutnar, Aleksander Malnič, Dragan Marušič, 2012, original scientific article Abstract: In 1969, Lovász asked if every finite, connected vertex-transitive graph has a Hamilton path. In spite of its easy formulation, no major breakthrough has been achieved thus far, and the problem is now commonly accepted to be very hard. The same holds for the special subclass of Cayley graphs where the existence of Hamilton cycles has been conjectured. In 2007, Glover and Marušič proved that a cubic Cayley graph on a finite ▫$(2, s, 3)$▫-generated group ▫$G = \langle a, x| a^2 = x^s = (ax)^3 = 1, \dots \rangle$▫ has a Hamilton path when ▫$|G|$▫ is congruent to 0 modulo 4, and has a Hamilton cycle when ▫$|G|$▫ is congruent to 2 modulo 4. The Hamilton cycle was constructed, combining the theory of Cayley maps with classical results on cyclic stability in cubic graphs, as the contractible boundary of a tree of faces in the corresponding Cayley map. With a generalization of these methods, Glover, Kutnar and Marušič in 2009 resolved the case when, apart from ▫$|G|$▫, also ▫$s$▫ is congruent to 0 modulo 4. In this article, with a further extension of the above "tree of faces" approach, a Hamilton cycle is shown to exist whenever ▫$|G|$▫ is congruent to 0 modulo 4 and s is odd. This leaves ▫$|G|$▫ congruent to 0 modulo 4 with s congruent to 2 modulo 4 as the only remaining open case. In this last case, however, the "tree of faces" approach cannot be applied, and so entirely different techniques will have to be introduced if one is to complete the proof of the existence of Hamilton cycles in cubic Cayley graphs arising from finite ▫$(2, s, 3)$▫-generated groups.
Keywords: Cayley graph, Hamilton cycle, arc-transitive graph, 1-regular action, automorphism group
Published in RUP: 15.10.2013; Views: 3046; Downloads: 133
Link to full text |
