11. Hamilton cycles in (2, odd, 3)-Cayley graphsHenry Glover, Klavdija Kutnar, Aleksander Malnič, Dragan Marušič, 2012, izvirni znanstveni članek Opis: 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. Najdeno v: osebi Ključne besede: Cayley graph, Hamilton cycle, arc-transitive graph, 1-regular action, automorphism group Objavljeno: 15.10.2013; Ogledov: 1197; Prenosov: 54 Polno besedilo (0,00 KB) |
12. On the split structure of lifted groupsAleksander Malnič, Rok Požar, 2016, izvirni znanstveni članek Najdeno v: osebi Ključne besede: algorithm, abelian cover, Cayley voltages, covering projection, graph, group extension, group presentation, lifting automorphisms, linear systems over the integers, semidirect product Objavljeno: 15.10.2015; Ogledov: 961; Prenosov: 52 Polno besedilo (0,00 KB) |
13. Reachability relations in digraphsNorbert Seifter, Boris Zgrablić, Aleksander Malnič, Primož Šparl, Dragan Marušič, 2008, izvirni znanstveni članek Opis: In this paper we study reachability relations on vertices of digraphs, informally defined as follows. First, the weight of a walk is equal to the number of edges traversed in the direction coinciding with their orientation, minus the number of edges traversed in the direction opposite to their orientation. Then, a vertex ▫$u$▫ is ▫$R_k^+$▫-related to a vertex ▫$v$▫ if there exists a 0-weighted walk from ▫$u$▫ to ▫$v$▫ whose every subwalk starting at u has weight in the interval ▫$[0,k]$▫. Similarly, a vertex ▫$u$▫ is ▫$R_k^-$▫-related to a vertex ▫$v$▫ if there exists a 0-weighted walk from ▫$u$▫ to ▫$v$▫ whose every subwalk starting at ▫$u$▫ has weight in the interval ▫$[-k,0]$▫. For all positive integers ▫$k$▫, the relations ▫$R_k^+$▫ and ▫$R_k^-$▫ are equivalence relations on the vertex set of a given digraph. We prove that, for transitive digraphs, properties of these relations are closely related to other properties such as having property ▫$\mathbb{Z}$▫, the number of ends, growth conditions, and vertex degree. Najdeno v: osebi Ključne besede: graph theory, digraph, reachability relations, end of a graph, property ▫$\mathbb{Z}$▫, growth Objavljeno: 03.04.2017; Ogledov: 815; Prenosov: 72 Polno besedilo (0,00 KB) |
14. Minimal normal subgroups of transitive permutation groups of square-free degreeAleksander Malnič, Dragan Marušič, Edward Dobson, Lewis A. Nowitz, 2007, izvirni znanstveni članek Opis: It is shown that a minimal normal subgroup of a transitive permutation group of square-free degree in its induced action is simple and quasiprimitive, with three exceptions related to ▫$A_5$▫, ▫$A_7$▫, and PSL(2,29). Moreover, it is shown that a minimal normal subgroup of a 2-closed permutation group of square-free degree in its induced action is simple. As an almost immediate consequence, it follows that a 2-closed transitive permutation group of square-free degree contains a semiregular element of prime order, thus giving a partial affirmative answer to the conjecture 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]). Najdeno v: osebi Ključne besede: mathematics, graph theory, transitive permutation group, 2-closed group, square-free degree, semiregular automorphism, vertex-transitive graph Objavljeno: 03.04.2017; Ogledov: 835; Prenosov: 43 Polno besedilo (0,00 KB) |
15. Symmetry structure of bicirculantsBoštjan Frelih, Primož Šparl, Aleksander Malnič, Dragan Marušič, 2007, izvirni znanstveni članek Opis: An ▫$n$▫-bicirculant is a graph having an automorphism with two orbits of length ▫$n$▫ and no other orbits. Symmetry properties of ▫$p$▫-bicirculants, ▫$p$▫ a prime, are extensively studied. In particular, the actions of their automorphism groups are described in detail in terms of certain algebraic representation of such graphs. Najdeno v: osebi Ključne besede: mathematics, graph theory, graph, circulant, bicirculant, automorphism group Objavljeno: 03.04.2017; Ogledov: 944; Prenosov: 49 Polno besedilo (0,00 KB) |
16. On strongly regular bicirculantsDragan Marušič, Aleksander Malnič, Primož Šparl, 2007, izvirni znanstveni članek Opis: An ▫$n$▫-bicirculantis a graph having an automorphism with two orbits of length ▫$n$▫ and no other orbits. This article deals with strongly regular bicirculants. It is known that for a nontrivial strongly regular ▫$n$▫-bicirculant, ▫$n$▫ odd, there exists a positive integer m such that ▫$n=2m^2+2m+1▫$. Only three nontrivial examples have been known previously, namely, for ▫$m=1,2$▫ and 4. Case ▫$m=1$▫ gives rise to the Petersen graph and its complement, while the graphs arising from cases ▫$m=2$▫ and ▫$m=4$▫ are associated with certain Steiner systems. Similarly, if ▫$n$▫ is even, then ▫$n=2m^2$▫ for some ▫$m \ge 2$▫. Apart from a pair of complementary strongly regular 8-bicirculants, no other example seems to be known. A necessary condition for the existence of a strongly regular vertex-transitive ▫$p$▫-bicirculant, ▫$p$▫ a prime, is obtained here. In addition, three new strongly regular bicirculants having 50, 82 and 122 vertices corresponding, respectively, to ▫$m=3,4$▫ and 5 above, are presented. These graphs are not associated with any Steiner system, and together with their complements form the first known pairs of complementary strongly regular bicirculants which are vertex-transitive but not edge-transitive. Najdeno v: osebi Ključne besede: mathematics, graph theory, graph, circulant, bicirculant, automorphism group Objavljeno: 03.04.2017; Ogledov: 971; Prenosov: 43 Polno besedilo (0,00 KB) |
17. Semiregular automorphisms of vertex-transitive graphs of certain valenciesDragan Marušič, Edward Dobson, Aleksander Malnič, Lewis A. Nowitz, 2007, izvirni znanstveni članek Opis: 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]). Najdeno v: osebi Ključne besede: mathematics, graph theory, transitive permutation group, 2-closed group, semiregular automorphism, vertex-transitive graph Objavljeno: 03.04.2017; Ogledov: 798; Prenosov: 39 Polno besedilo (0,00 KB) |
18. Semisymmetric elementary abelian covers of the Möbius-Kantor graphAleksander Malnič, Štefko Miklavič, Primož Potočnik, Dragan Marušič, 2007, izvirni znanstveni članek Opis: Let ▫$\wp_N : \tilde{X} \to X$▫ be a regular covering projection of connected graphs with the group of covering transformations isomorphic to ▫$N$▫. If ▫$N$▫ is an elementary abelian ▫$p$▫-group, then the projection ▫$\wp_N$▫ is called ▫$p$▫-elementary abelian. The projection ▫$\wp_N$▫ is vertex-transitive (edge-transitive) if some vertex-transitive (edge-transitive) subgroup of Aut ▫$X$▫ lifts along ▫$\wp_N$▫, and semisymmetric if it is edge- but not vertex-transitive. The projection ▫$\wp_N$▫ is minimal semisymmetric if ▫$\wp_N$▫ cannot be written as a composition ▫$\wp_N = \wp \circ \wp_M$▫ of two (nontrivial) regular covering projections, where ▫$\pw_M$▫ is semisymmetric. Finding elementary abelian covering projections can be grasped combinatorially via a linear representation of automorphisms acting on the first homology group of the graph. The method essentially reduces to finding invariant subspaces of matrix groups over prime fields (see [A. Malnic, D. Marušic, P. Potocnik, Elementary abelian covers of graphs, J. Algebraic Combin. 20 (2004) 71-97]). In this paper, all pairwise nonisomorphic minimal semisymmetric elementary abelian regular covering projections of the Möbius-Kantor graph, the Generalized Petersen graph GP(8,3), are constructed. No such covers exist for ▫$p=2$▫. Otherwise, the number of such covering projections is equal to ▫$(p-1)/4$▫ and ▫$1+(p-1)/4$▫ in cases ▫$p \equiv 5,9,13,17,21 \pmod{24}$▫ and ▫$p \equiv 1 \pmod{24}$▫, respectively, and to ▫$(p+1)/4$▫ and ▫$1+(p+1)/4$▫ in cases ▫$p \equiv 3,7,11,15,23 \pmod{24}$▫ and ▫$p \equiv 19 \pmod{24}$▫, respectively. For each such covering projection the voltage rules generating the corresponding covers are displayed explicitly. Najdeno v: osebi Ključne besede: mathematics, graph theory, graph, covering projection, lifting automorphisms, homology group, group representation, matrix group, invariant subspaces Objavljeno: 03.04.2017; Ogledov: 747; Prenosov: 43 Polno besedilo (0,00 KB) |
19. |
20. |