Search

Given a graph X with a Hamilton cycle C, the compression factor κ (X , C) of C is the order of the largest cyclic subgroup of Aut (C) ∩ Aut (X) , and the Hamilton compression κ (X) of X is the maximum of κ (X , C) where C runs over all Hamilton cycles in X. Generalizing the well-known open problem regarding the existence of vertex-transitive graphs without Hamilton paths/cycles, it was asked by Gregor et al. (Ann Comb, arXiv:2205.08126v1, https://doi.org/10.1007/s00026-023-00674-y, 2023) whether for every positive integer k, there exists infinitely many vertex-transitive graphs (Cayley graphs) with Hamilton compression equal to k. Since an infinite family of Cayley graphs with Hamilton compression equal to 1 was given there, the question is completely resolved in this paper in the case of Cayley graphs with a construction of Cayley graphs of semidirect products Z p ⋊ Z k where p is a prime and k ≥ 2 a divisor of p - 1 . Further, infinite families of non-Cayley vertex-transitive graphs with Hamilton compression equal to 1 are given. All of these graphs being metacirculants, some additional results on Hamilton compression of metacirculants of specific orders are also given. [ABSTRACT FROM AUTHOR]

A cycle in a graph is consistent if the automorphism group of the graph admits a one‐step rotation of this cycle. A thorough description of consistent cycles of arc‐transitive subgroups in the full automorphism groups of finite cubic symmetric graphs is given. [ABSTRACT FROM AUTHOR]

An automorphism ρ of a graph X is said to be semiregular provided all of its cycles in its cycle decomposition are of the same length, and is said to be simplicial if it is semiregular and the quotient multigraph X ρ of X with respect to ρ is a simple graph, and thus of the same valency as X. It is shown that, with the exception of the complete graph K 4 , the Petersen graph, the Coxeter graph and the so called H-graph (alternatively denoted as S (17) , the smallest graph in the family of the so called Sextet graphs S (p) , p ≡ ± 1 (mod 16)), every cubic arc-transitive graph with a primitive automorphism group admits a simplicial automorphism. [ABSTRACT FROM AUTHOR]

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=〈 a, x| a2=xs=(ax)3=1, … 〉 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. [ABSTRACT FROM PUBLISHER]

Abstract: A complete classification of cubic symmetric graphs of girth 6 is given. It is shown that with the exception of the Heawood graph, the Moebius–Kantor graph, the Pappus graph, and the Desargues graph, a cubic symmetric graph X of girth 6 is a normal Cayley graph of a generalized dihedral group; in particular, [(i)] X is 2-regular if and only if it is isomorphic to a so-called -path, a graph of order either or , which is characterized by the fact that its quotient relative to a certain semiregular automorphism is a path. [(ii)] X is 1-regular if and only if there exists an integer r with prime decomposition , where , , and , such that X is isomorphic either to a Cayley graph of a dihedral group of order 2r or X is isomorphic to a certain -cover of one of the following graphs: the cube , the Pappus graph or an -path of order . [Copyright &y& Elsevier]

Following a problem posed by Lovász in 1969, it is believed that every finite connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from finite groups having a (2, s, 3)-presentation, that is, for groups G = (a, b ǀ a2 = 1, bs = 1, (ab)3 = 1, ...) generated by an involution a and an element b of order s ⩾ 3 such that their product ab has order 3. More precisely, it is shown that the Cayley graph X = Cay(G, {a, b, b-1 }) has a Hamilton cycle when ǀGǀ (and thus s) is congruent to 2 modulo 4, and has a long cycle missing only two adjacent vertices (and thus necessarily a Hamilton path) when ǀGǀ is congruent to 0 modulo 4. [ABSTRACT FROM AUTHOR]

The classification of 2-arc-transitive Cayley graphs of cyclic groups, given in (J. Algebra. Combin. 5 (1996) 83–86) by Alspach, Conder, Xu and the author, motivates the main theme of this article: the study of 2-arc-transitive Cayley graphs of dihedral groups. First, a previously unknown infinite family of such graphs, arising as covers of certain complete graphs, is presented, leading to an interesting property of Singer cycles in the group PGL(2,q), q an odd prime power, among others. Second, a structural reduction theorem for 2-arc-transitive Cayley graphs of dihedral groups is proved, putting us—modulo a possible existence of such graphs among regular cyclic covers over a small family of certain bipartite graphs—a step away from a complete classification of such graphs. As a byproduct, a partial description of 2-arc-transitive Cayley graphs of abelian groups with at most three involutions is also obtained. [Copyright &y& Elsevier]

A classification of all 2-arc-transitive graphs of order a product of two primes is given. Furthermore, it is shown that cycles and complete graphs are the only 2-arc-transitive Cayley graph of Abelian group of odd order. [Copyright &y& Elsevier]

Following Hujdurović et al. (2016), an automorphism of a graph is said to be even/odd if it acts on the vertex set of the graph as an even/odd permutation. In this paper the formula for calculating the number of graphs of order n admitting odd automorphisms and the formula for calculating the number of graphs of order n without odd automorphisms are given together with their asymptotic estimates. Such numbers are also considered for the subclass of vertex-transitive graphs. A positive integer n is a Cayley number if every vertex-transitive graph of order n is a Cayley graph. In analogy, a positive integer n is said to be a vertex-transitive-odd number (in short, a VTO-number ) if every vertex-transitive graph of order n admits an odd automorphism. It is proved that there exists infinitely many VTO numbers which are square-free and have arbitrarily long prime factorizations. Further, it is proved that Cayley numbers congruent to 2 modulo 4, cubefree nilpotent Cayley numbers congruent to 3 modulo 4, and numbers of the form 2 p , p a prime, are VTO numbers. At the other extreme, it is proved that for a positive integer n the complete graph K n and its complement are the only vertex-transitive graphs of order n admitting odd automorphisms if and only if n is a Fermat prime. [ABSTRACT FROM AUTHOR]

Let G be a finite group and X a (di)graph. If there exists a semiregular subgroup G ¯ of the automorphism group  Aut( X ) isomorphic to G with n orbits on V ( X ) then the (di)graph X is called an n - Cayley graph on G . If, in addition, this subgroup G ¯ is normal in  Aut( X ) then X is called a normal n-Cayley graph on G . In this paper the normalizers of semiregular subgroups of the automorphism group of a digraph are characterized. It is proved that every finite group admits a vertex-transitive normal n -Cayley graph for every n  ≥ 2. For the most part the graphs are constructed as Cartesian product of graphs. It is proved that a Cartesian product of two relatively prime graphs is Cayley (resp. normal Cayley) if and only if the factor graphs are Cayley (resp. normal Cayley). In addition, the concept of graphical regular representations (GRRs) is generalized to n -GRR in a natural way, and it is proved that any group admitting a GRR also admits an n -GRR for any n  ≥ 1. [ABSTRACT FROM AUTHOR]

The concept of generalized Cayley graphs was introduced by Marušič et al. (1992), where it was asked if there exists a vertex-transitive generalized Cayley graph which is not a Cayley graph. In this paper the question is answered in the affirmative with a construction of two infinite families of such graphs. It is also proven that every generalized Cayley graph admits a semiregular automorphism. [ABSTRACT FROM AUTHOR]

For a permutation group G acting on a set V , a subset I of G is said to be an intersecting set if for every pair of elements g , h ∈ I there exists v ∈ V such that g (v) = h (v). The intersection density ρ (G) of a transitive permutation group G is the maximum value of the quotient | I | / | G v | where G v is a stabilizer of a point v ∈ V and I runs over all intersecting sets in G. If G v is the largest intersecting set in G then G is said to have the Erdős–Ko–Rado (EKR)-property , and moreover, G has the strict-EKR-property if every intersecting set of maximum size in G is a coset of a point stabilizer. Intersecting sets in G coincide with independent sets in the so-called derangement graph Γ G , defined as the Cayley graph on G with connection set consisting of all derangements, that is, fixed-point free elements of G. In this paper a conjecture regarding the existence of transitive permutation groups whose derangement graphs are complete multipartite graphs, posed by Meagher, Razafimahatratra and Spiga in Meagher et al. (2021) is proved. The proof uses direct product of groups. Questions regarding maximum intersecting sets in direct and wreath products of groups and the (strict)-EKR-property of these group products are also investigated. In addition, some errors appearing in the literature on this topic are corrected. [ABSTRACT FROM AUTHOR]

Abstract: A bi-Cayley graph is a graph which admits a semiregular group of automorphisms with two orbits (of equal size), and is a one-matching bi-Cayley graph if the bipartite graph induced by the edges joining these two orbits is a perfect matching. Typical examples of such graphs are the generalized Petersen graphs. A classification of connected arc-transitive one-matching bi-Cayley graphs over abelian groups is given. This is done without referring to the classification of finite simple groups. Instead, complex irreducible characters of abelian groups are used extensively. [Copyright &y& Elsevier]

Abstract: The results of Širáň and the first author [A construction of vertex-transitive non-Cayley graphs, Australas. J. Combin. 10 (1994) 105–114; More constructions of vertex-transitive non-Cayley graphs based on counting closed walks, Australas. J. Combin. 14 (1996) 121–132] are generalized, and new formulas for the number of closed walks of length or pq, where p and q are primes, valid for all vertex-transitive graphs are found. Based on these formulas, several simple tests for vertex-transitivity are presented, as well as lower bounds on the orders of the smallest vertex- and arc-transitive groups of automorphisms for vertex-transitive graphs of given valence. [Copyright &y& Elsevier]

It was proved in Feng et al. (2015) that a cubic symmetric graph with a solvable automorphism group is either a Cayley graph or a 2-regular graph of type 2 2 , that is, a graph with no automorphism of order 2 interchanging two adjacent vertices. In this paper an infinite family of non-Cayley cubic 2-regular graphs of type 2 2 with a solvable automorphism group is constructed, and the smallest graph has order 6174. This answers a question posed by Estélyi and Pisanski in 2016. Moreover, it includes a subfamily of graphs which are connected 2-regular covers of the Pappus graph with covering transformation group Z p 3 , and these graphs were missed in Oh (2009). [ABSTRACT FROM AUTHOR]

Abstract: As a generalization of undirected strongly regular graphs, a digraph X without loops, of valency k and order v is said to be a -directed strongly regular graph whenever for any vertex u of X there are t undirected edges having u as an endvertex and for every two different vertices u and w of X the number of paths of length 2 starting at u and ending at w is λ or μ depending only on whether uw is an arc of X or not. An m-Cayley digraph of a group H is a digraph admitting a semiregular group of automorphisms having m orbits, all of equal length, isomorphic to H. In this paper, the structure of directed strongly regular 2-Cayley graphs of cyclic groups is investigated. In particular, the arithmetic conditions on parameters v, k, μ, λ, and t are given. Also, several infinite families of directed strongly regular graphs which are also 2-Cayley digraphs of abelian groups are constructed. [Copyright &y& Elsevier]

Abstract: In this paper, bounds for the edge connectivity of -Cayley graphs are found, and also several structural conditions are given for a connected -regular bi-abelian graph to have edge connectivity strictly less than . Finally, two infinite families of partial sum families that generate directed strongly regular graphs with new parameters are shown. [Copyright &y& Elsevier]