Search

A graph $\Gamma $ is called $(G, s)$ -arc-transitive if $G \le \text{Aut} (\Gamma)$ is transitive on the set of vertices of $\Gamma $ and the set of s-arcs of $\Gamma $ , where for an integer $s \ge 1$ an s-arc of $\Gamma $ is a sequence of $s+1$ vertices $(v_0,v_1,\ldots ,v_s)$ of $\Gamma $ such that $v_{i-1}$ and $v_i$ are adjacent for $1 \le i \le s$ and $v_{i-1}\ne v_{i+1}$ for $1 \le i \le s-1$. A graph $\Gamma $ is called 2-transitive if it is $(\text{Aut} (\Gamma), 2)$ -arc-transitive but not $(\text{Aut} (\Gamma), 3)$ -arc-transitive. A Cayley graph $\Gamma $ of a group G is called normal if G is normal in $\text{Aut} (\Gamma)$ and nonnormal otherwise. Fang et al. ['On edge transitive Cayley graphs of valency four', European J. Combin.25 (2004), 1103–1116] proved that if $\Gamma $ is a tetravalent 2-transitive Cayley graph of a finite simple group G, then either $\Gamma $ is normal or G is one of the groups $\text{PSL}_2(11)$ , ${\rm M} _{11}$ , $\text{M} _{23}$ and $A_{11}$. However, it was unknown whether $\Gamma $ is normal when G is one of these four groups. We answer this question by proving that among these four groups only $\text{M} _{11}$ produces connected tetravalent 2-transitive nonnormal Cayley graphs. We prove further that there are exactly two such graphs which are nonisomorphic and both are determined in the paper. As a consequence, the automorphism group of any connected tetravalent 2-transitive Cayley graph of any finite simple group is determined. [ABSTRACT FROM AUTHOR]

The canonical double cover D(Γ) of a graph Γ is the direct product of Γ and K2. If Aut(D(Γ))≅Aut(Γ)×Z2 then Γ is called stable; otherwise Γ is called unstable. An unstable graph is said to be nontrivially unstable if it is connected, non‐bipartite and no two vertices have the same neighborhood. In 2008 Wilson conjectured that, if the generalized Petersen graph GP(n,k) is nontrivially unstable, then both n and k are even, and either n/2 is odd and k2≡±1(mod n/2), or n=4k. In this note we prove that this conjecture is true. At the same time we determine all possible isomorphisms among the generalized Petersen graphs, the canonical double covers of the generalized Petersen graphs, and the double generalized Petersen graphs. Based on these we completely determine the full automorphism group of the canonical double cover of GP(n,k) for any pair of integers n,k with 1⩽k

Let Γ be a graph with vertex set V ( Γ ). A subset C of V ( Γ ) is called a perfect code in Γ if C is an independent set of Γand every vertex in V ( Γ ) \ C is adjacent to exactly one vertex in C. A subset C of a group G is called a perfect code of G if there exists a Cayley graph of G which admits C as a perfect code. A group G is said to be code-perfect if every proper subgroup of G is a perfect code of G. In this paper we prove that a group is code-perfect if and only if it has no elements of order 4. We also prove that a proper subgroup H of an abelian group G is a perfect code of G if and only if the Sylow 2-subgroup of H is a perfect code of the Sylow 2-subgroup of G. This reduces the problem of determining when a given subgroup of an abelian group is a perfect code to the case of abelian 2-groups. Finally, we determine all subgroup perfect codes in any generalized quaternion group. [ABSTRACT FROM AUTHOR]