Search

Tutte's 3-flow conjecture asserts that every 4-edge-connected graph admits a nowhere-zero 3-flow. We prove that this conjecture is true for every Cayley graph of valency at least four on any supersolvable group with a noncyclic Sylow 2-subgroup and every Cayley graph of valency at least four on any group whose derived subgroup is of square-free order. [ABSTRACT FROM AUTHOR]

Metacirculants are a basic and well-studied family of vertex-transitive graphs, and weak metacirculants are generalizations of them. A graph is called a weak metacirculant if it has a vertex-transitive metacyclic automorphism group. This paper is devoted to the study of weak metacirculants with odd prime power order. We first prove that a weak metacirculant of odd prime power order is a metacirculant if and only if it has a vertex-transitive split metacyclic automorphism group. We then prove that for any odd prime p and integer ℓ ≥ 4 , there exist weak metacirculants of order p ℓ which are Cayley graphs but not Cayley graphs of any metacyclic group; this answers a question in Li et al. (2013) [11] We construct such graphs explicitly by introducing a construction which is a generalization of generalized Petersen graphs. Finally, we determine all smallest possible metacirculants of odd prime power order which are Cayley graphs but not Cayley graphs of any metacyclic group. [ABSTRACT FROM AUTHOR]

Abstract: A Frobenius group is a transitive but not regular permutation group such that only the identity element can fix two points. A finite Frobenius group can be expressed as with a nilpotent normal subgroup. A first-kind -Frobenius graph is a Cayley graph on with connection set an -orbit on generating , where is of even order or consists of involutions. We classify all 6-valent first-kind Frobenius circulant graphs such that the underlying kernel is cyclic. We give optimal gossiping and routing algorithms for such a circulant and compute its forwarding indices, Wiener indices and minimum gossip time. We also prove that its broadcasting time is equal to its diameter plus two or three. We prove that all 6-valent first-kind Frobenius circulants with cyclic kernels are Eisenstein–Jacobi graphs, the latter being Cayley graphs on quotient rings of the ring of Eisenstein–Jacobi integers. We also prove that larger Eisenstein–Jacobi graphs can be constructed from smaller ones as topological covers, and a similar result holds for 6-valent first-kind Frobenius circulants. As a corollary any Eisenstein–Jacobi graph with order congruent to 1 modulo 6 and underlying Eisenstein–Jacobi integer not an associate of a real integer, is a cover of a 6-valent first-kind Frobenius circulant. A distributed real-time computing architecture known as HARTS or hexagonal mesh is a special 6-valent first-kind Frobenius circulant. [Copyright &y& Elsevier]

We correct the statements of two theorems and two corollaries in our paper Zhang and Zhou (2021). Proofs of these theorems and three other results are given as well. [ABSTRACT FROM AUTHOR]

Abstract: A Frobenius group is a permutation group which is transitive but not regular such that only the identity element can fix two points. It is well known that such a group is a semidirect product , where is a nilpotent normal subgroup of . A second-kind -Frobenius graph is a Cayley graph for some with order and , where is of odd order and denotes the -orbit containing . In the case when is abelian of odd order, we give the exact value of the minimum gossiping time of under the store-and-forward, all-port and full-duplex model and prove that admits optimal gossiping schemes with the following properties: messages are always transmitted along shortest paths; each arc is used exactly once at each time step; at each step after the initial one the arcs carrying the message originated from a given vertex form a perfect matching. In the case when is abelian of even order, we give an upper bound on the minimum gossiping time of under the same model. When is abelian, we give an algorithm for producing all-to-all routings which are optimal for both edge-forwarding and minimal edge-forwarding indices of , and prove that such routings are also optimal for arc-forwarding and minimal arc-forwarding indices if in addition is of odd order. We give a family of second-kind Frobenius graphs which contains all Paley graphs and connected generalized Paley graphs of odd order as a proper subfamily. Based on this and Dirichlet’s prime number theorem we show that, for any even integer , there exist infinitely many second-kind Frobenius graphs with valency and order greater than any given integer such that the kernels of the underlying Frobenius groups are abelian of odd order. [Copyright &y& Elsevier]

Abstract: Let be a -symmetric graph, and let be a nontrivial -invariant partition of the vertex set of . This paper aims to characterize under the conditions that the quotient graph is -arc transitive and the induced subgraph between two adjacent blocks is or . The results answer two questions about the relationship between and for this class of graphs. [Copyright &y& Elsevier]

We find a natural construction of a large class of symmetric graphs from point- and block-transitive 1-designs. The graphs in this class can be characterized as G -symmetric graphs whose vertex sets admit a G -invariant partition B of block size at least 3 such that, for any two blocks B, C of B, either there is no edge between B and C, or there exists only one vertex in B not adjacent to any vertex inC . The special case where the quotient graph ΓBof Γ relative to B is a complete graph occurs if and only if the 1-design needed in the construction is a G -doubly transitive and G -block-transitive 2-design, and in this case we give an explicit classification of Γ when G is a doubly transitive projective group or an affine group containing the affine general group. Examples of such graphs include cross ratio graphs studied recently by Gardiner, Praeger and Zhou and some other graphs with vertices the (point, line)-flags of the projective or affine geometry. [Copyright &y& Elsevier]

A graphical regular representation (GRR) of a group G is a Cayley graph of G whose full automorphism group is equal to the right regular permutation representation of G. In this paper we study cubic GRRs of PSL n (q) (n = 4 , 6 , 8), PSp n (q) (n = 6 , 8), P Ω n + (q) (n = 8 , 10 , 12) and P Ω n − (q) (n = 8 , 10 , 12), where q = 2 f with f ≥ 1. We prove that for each of these groups, with probability tending to 1 as q → ∞ , any element x of odd prime order dividing 2 e f − 1 but not 2 i − 1 for each 1 ≤ i < e f together with a random involution y gives rise to a cubic GRR, where e = n − 2 for P Ω n + (q) and e = n for other groups. Moreover, for sufficiently large q , there are elements x satisfying these conditions, and for each of them there exists an involution y such that { x , x − 1 , y } produces a cubic GRR. This result together with certain known results in the literature implies that except for PSL 2 (q) , PSL 3 (q) , PSU 3 (q) and a finite number of other cases, every finite non-abelian simple group contains an element x and an involution y such that { x , x − 1 , y } produces a GRR, showing that a modified version of a conjecture by Spiga is true. Our results and several known results together also confirm a conjecture by Fang and Xia which asserts that except for a finite number of cases every finite non-abelian simple group has a cubic GRR. [ABSTRACT FROM AUTHOR]

We study the normal Cayley graphs Cay (S n , C (n , I)) on the symmetric group S n , where I ⊆ { 2 , 3 , ... , n } and C (n , I) is the set of all cycles in S n with length in I. We prove that the strictly second largest eigenvalue of Cay (S n , C (n , I)) can only be achieved by at most four irreducible representations of S n , and we determine further the multiplicity of this eigenvalue in several special cases. As a corollary, in the case when I contains neither n − 1 nor n we know exactly when Cay (S n , C (n , I)) has the Aldous property, namely the strictly second largest eigenvalue is attained by the standard representation of S n , and we obtain that Cay (S n , C (n , I)) does not have the Aldous property whenever n ∈ I. As another corollary of our main results, we prove a recent conjecture on the second largest eigenvalue of Cay (S n , C (n , { k })) where 2 ≤ k ≤ n − 2. [ABSTRACT FROM AUTHOR]

A perfect code in a graph Γ = (V , E) is a subset C of V such that no two vertices in C are adjacent and every vertex in V ∖ C is adjacent to exactly one vertex in C. A subgroup H of a group G is called a subgroup perfect code of G if there exists a Cayley graph of G which admits H as a perfect code. Equivalently, H is a subgroup perfect code of G if there exists an inverse-closed subset A of G containing the identity element such that (A , H) is a tiling of G in the sense that every element of G can be uniquely expressed as the product of an element of A and an element of H. In this paper we obtain multiple results on subgroup perfect codes of finite groups, including a few necessary and sufficient conditions for a subgroup of a finite group to be a subgroup perfect code, a few results involving 2-subgroups in the study of subgroup perfect codes, and several results on subgroup perfect codes of metabelian groups, generalized dihedral groups, nilpotent groups and 2-groups. [ABSTRACT FROM AUTHOR]

A reductive characterization of arc-transitive circulants was given independently by Kovács in 2004 and the first author in 2005. In this paper, we give an explicit characterization of arc-transitive circulants and their automorphism groups. Based on this, we give a proof of the fact that arc-transitive circulants are all CI-digraphs. [ABSTRACT FROM AUTHOR]

Abstract The canonical double cover D (Γ) of a graph Γ is the direct product of Γ and K 2. If Aut (D (Γ)) = Aut (Γ) × Z 2 then Γ is called stable; otherwise Γ is called unstable. An unstable graph is nontrivially unstable if it is connected, non-bipartite and distinct vertices have different neighborhoods. In this paper we prove that every circulant graph of odd prime order is stable and there is no arc-transitive nontrivially unstable circulant graph. The latter answers a question of Wilson in 2008. We also give infinitely many counterexamples to a conjecture of Marušič, Scapellato and Zagaglia Salvi in 1989 by constructing a family of stable circulant graphs with compatible adjacency matrices. [ABSTRACT FROM AUTHOR]

Abstract Hadwiger's conjecture asserts that any graph contains a clique minor with order no less than the chromatic number of the graph. We prove that this well-known conjecture is true for all graphs if and only if it is true for squares of split graphs. This observation implies that Hadwiger's conjecture for squares of chordal graphs is as difficult as the general case, since chordal graphs are a superclass of split graphs. Then we consider 2-trees which are a subclass of each of planar graphs, 2-degenerate graphs and chordal graphs. We prove that Hadwiger's conjecture is true for squares of 2-trees. We achieve this by proving the following stronger result: for any 2-tree T , its square T 2 has a clique minor of order χ (T 2) for which each branch set induces a path, where χ (T 2) is the chromatic number of T 2. [ABSTRACT FROM AUTHOR]

Aldous' spectral gap conjecture states that the second largest eigenvalue of any connected Cayley graph on the symmetric group S n with respect to a set of transpositions is achieved by the standard representation of S n. This celebrated conjecture, which was proved in its general form in 2010, has inspired much interest in searching for other families of Cayley graphs on S n with the property that the largest eigenvalue strictly smaller than the degree is attained by the standard representation of S n. In this paper, we prove three results on normal Cayley graphs on S n possessing this property for sufficiently large n , one of which can be viewed as a generalization of the "normal" case of Aldous' spectral gap conjecture. [ABSTRACT FROM AUTHOR]

Abstract: Let be an integer. An -labelling of a (finite or infinite) graph is an assignment of nonnegative integers (labels) to its vertices such that adjacent vertices receive labels with difference at least , and vertices distance 2 or 3 apart receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used, and the minimum span over all -labellings is called the -number of the graph. We prove that, for any integer and any finite tree of diameter at least 3 or infinite tree of finite maximum degree, , and both lower and upper bounds are attainable, where is the maximum total degree of two adjacent vertices. Moreover, if is less than or equal to the minimum degree of a non-pendant vertex of , then . In particular, . Furthermore, if is a caterpillar and , then with both lower and upper bounds achievable. [Copyright &y& Elsevier]

Abstract: Let be a graph admitting an arc-transitive subgroup of automorphisms that leaves invariant a vertex partition with parts of size . In this paper we study such graphs where: for connected by some edge of , exactly two vertices of lie on no edge with a vertex of ; and as runs over all parts of connected to these vertex pairs (ignoring multiplicities) form a cycle. We prove that this occurs if and only if or 4, and moreover we give three geometric or group theoretic constructions of infinite families of such graphs. [Copyright &y& Elsevier]

Abstract: This paper forms part of a study of 2-arc transitivity for finite imprimitive symmetric graphs, namely for graphs admitting an automorphism group G that is transitive on ordered pairs of adjacent vertices, and leaves invariant a nontrivial vertex partition . Such a group G is also transitive on the ordered pairs of adjacent vertices of the quotient graph corresponding to . If in addition G is transitive on the 2-arcs of (that is, on vertex triples such that and are adjacent and ), then G is not in general transitive on the 2-arcs of , although it does have this property in the special case where is the orbit set of a vertex-intransitive normal subgroup of G. On the other hand, G is sometimes transitive on the 2-arcs of even if it is not transitive on the 2-arcs of . We study conditions under which G is transitive on the 2-arcs of . Our conditions relate to the structure of the bipartite graph induced on for adjacent blocks of , and a graph structure induced on B. We obtain necessary and sufficient conditions for G to be transitive on the 2-arcs of one or both of for certain families of imprimitive symmetric graphs. [Copyright &y& Elsevier]

We start up the study of the stability of general graph pairs. This notion is a generalization of the concept of the stability of graphs. We say that a pair of graphs (Γ , Σ) is stable if Aut (Γ × Σ) ≅ Aut (Γ) × Aut (Σ) and unstable otherwise, where Γ × Σ is the direct product of Γ and Σ. An unstable graph pair (Γ , Σ) is said to be a nontrivially unstable graph pair if Γ and Σ are connected coprime graphs, at least one of them is non-bipartite, and each of them has the property that different vertices have distinct neighborhoods. We obtain necessary conditions for a pair of graphs to be stable. We also give a characterization of a pair of graphs (Γ , Σ) to be nontrivially unstable in the case when both graphs are connected and regular with coprime valencies and Σ is vertex-transitive. This characterization is given in terms of the Σ-automorphisms of Γ, which are a new concept introduced in this paper as a generalization of both automorphisms and two-fold automorphisms of a graph. [ABSTRACT FROM AUTHOR]

A graph Γ is called G -symmetric if it admits G as a group of automorphisms acting transitively on the set of ordered pairs of adjacent vertices. We give a classification of G -symmetric graphs Γ with V ( Γ ) admitting a nontrivial G -invariant partition B such that there is exactly one edge of Γ between any two distinct blocks of B . This is achieved by giving a classification of ( G , 2 ) -point-transitive and G -block-transitive designs D together with G -orbits Ω on the flag set of D such that G σ , L is transitive on L ∖ { σ } and L ∩ N = { σ } for distinct ( σ , L ) , ( σ , N ) ∈ Ω , where G σ , L is the setwise stabilizer of L in the stabilizer G σ of σ in G . Along the way we determine all imprimitive blocks of G σ on V ∖ { σ } for every 2-transitive group G on a set V , where σ ∈ V . [ABSTRACT FROM AUTHOR]