Tetravalent one-regular graphs of order 2<Emphasis Type="Italic">pq</Emphasis>

A graph is one-regular if its automorphism group acts regularly on the set of its arcs. In this article a complete classification of tetravalent one-regular graphs of order twice a product of two primes is given. It follows from this classification that with the exception of four graphs of orders 12 and 30, all such graphs are Cayley graphs on Abelian, dihedral, or generalized dihedral groups.     

Normality of Tetravalent Cayley Graphs of Odd Prime-cube Order and Its Application

Let p be an odd prime. In this paper we prove that all tetravalent connected Cayley graphs of order p^3 are normal. As an application, a classification of tetravalent symmetric graphs of odd prime-cube order is given.     

The edge-transitive tetravalent Cayley graphs of square-free order

A classification is given for connected edge-transitive tetravalent Cayley graphs of square-free order. The classification shows that, with a few exceptions, a connected edge-transitive tetravalent Cayley graph of square-free order is either arc-regular or edge-regular. It thus provides a generic construction of half-transitive graphs of valency 4.     

Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

3p阶亚循环群的连通4度Cayley图

研究3p阶(p是大于3的素数)亚循环群的连通4度Cayley图.主要决定了其全自同构群的结构,并由此得到这类图的CI性、正规性和弧传递性.用到单群分类定理.     

Tetravalent edge-transitive graphs of order p 2 q

A graph is called edge-transitive if its full automorphism group acts transitively on its edge set.In this paper,by using classification of finite simple groups,we classify tetravalent edge-transitive graphs of order p2q with p,q distinct odd primes.The result generalizes certain previous results.In particular,it shows that such graphs are normal Cayley graphs with only a few exceptions of small orders.     

Tetravalent half-arc-transitive graphs of order 2<Emphasis Type="Italic">pq</Emphasis>

A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not arc set. Let p and q be primes. It is known that no tetravalent half-arc-transitive graphs of order 2p ² exist and a tetravalent half-arc-transitive graph of order 4p must be non-Cayley; such a non-Cayley graph exists if and only if p−1 is divisible by 8 and it is unique for a given order. Based on the constructions of tetravalent half-arc-transitive graphs given by Marušič (J. Comb. Theory B 73:41–76, 1998), in this paper the connected tetravalent half-arc-transitive graphs of order 2pq are classified for distinct odd primes p and q.     

Tetravalent arc-transitive graphs of order twice a product of two primes

In this article a complete classification of tetravalent arc-transitive graphs of order twice a product of two primes is given.     

On Non-Cayley Tetravalent Metacirculant Graphs

 In connection with the classification problem for non-Cayley tetravalent metacirculant graphs, three families of special tetravalent metacirculant graphs, denoted by Φ₁, Φ₂ and Φ₃, have been defined [11]. It has also been shown [11] that any non-Cayley tetravalent metacirculant graph is isomorphic to a union of disjoint copies of a non-Cayley graph in one of the families Φ₁, Φ₂ or Φ₃. A natural question raised from the result is whether all graphs in these families are non-Cayley. We have proved recently in [12] that every graph in Φ₂ is non-Cayley. In this paper, we show that every graph in Φ₁ is also a connected non-Cayley graph and find an infinite class of connected non-Cayley graphs in the family Φ₃. Received: October, 2001 Final version received: July 29, 2002     

Symmetry properties of Cayley graphs of small valencies on the alternating group A_5

The normality of symmetry property of Cayley graphs of valencies 3 and 4 on the alternating group A5 is studied. We prove that all but four such graphs are normal; that A5 is not 5-CI. A complete classification of all arc-transitive Cayley graphs on A5 of valencies 3 and 4 as well as some examples of trivalent and tetravalent GRRs of A5 is given.     

Constructing even radius tightly attached half-arc-transitive graphs of valency four

A finite graph X is half-arc-transitive if its automorphism group is transitive on vertices and edges, but not on arcs. When X is tetravalent, the automorphism group induces an orientation on the edges and a cycle of X is called an alternating cycle if its consecutive edges in the cycle have opposite orientations. All alternating cycles of X have the same length and half of this length is called the radius of X. The graph X is said to be tightly attached if any two adjacent alternating cycles intersect in the same number of vertices equal to the radius of X. Marušič (J. Comb. Theory B, 73, 41–76, 1998) classified odd radius tightly attached tetravalent half-arc-transitive graphs. In this paper, we classify the half-arc-transitive regular coverings of the complete bipartite graph K _4,4 whose covering transformation group is cyclic of prime-power order and whose fibre-preserving group contains a half-arc-transitive subgroup. As a result, two new infinite families of even radius tightly attached tetravalent half-arc-transitive graphs are constructed, introducing the first infinite families of tetravalent half-arc-transitive graphs of 2-power orders.      

Tetravalent s-Transitive Graphs of Order 4p 2

Let s be a positive integer. A graph is s -transitive if its automorphism group is transitive on s-arcs but not on (s?+?1)-arcs. Let p be a prime. Zhou (Discrete Math 309:6081?C6086, 2009) classified tetravalent s-transitive graphs of order 4p. In this article a complete classification of tetravalent s-transitive graphs of order 4p ² is given.     

Symmetry properties of Cayley graphs of small valencies on the alternating group A<Subscript>5</Subscript>

The normality of symmetry property of Cayley graphs of valencies 3 and 4 on the alternating group A₅ is studied. We prove that all but four such graphs are normal; that A₅ is not 5-CI. A complete classification of all arc-transitive Cayley graphs on A₅ of valencies 3 and 4 as well as some examples of trivalent and tetravalent GRRs of A₅ is given.     

On the Cayley Graphs of Brandt Semigroups

In this article, the Cayley graphs of Brandt semigroups are investigated. The basic structures and properties of this kind of Cayley graphs are given, and a necessary and sufficient condition is given for the components of Cayley graphs of Brandt semigroups to be strongly regular. As an application, the generalized Petersen graph and k-partite graph, which cannot be obtained from the Cayley graphs of groups, can be constructed as a component of the Cayley graphs of Brandt semigroups.     

Mirror graphs: Graph theoretical characterization of reflection arrangements and finite Coxeter groups

Mirror graphs were introduced by Brešar et al. (2004) as an intriguing class of graphs: vertex-transitive, isometrically embeddable into hypercubes, having a strong connection with regular maps and polytope structure. In this article we settle the structure of mirror graphs by characterizing them as precisely the Cayley graphs of the finite Coxeter groups or equivalently the tope graphs of reflection arrangements—well understood and classified structures. We provide a polynomial algorithm for their recognition.     

Tetravalent Vertex-Transitive Graphs of Order Twice A Prime Square

A graph is vertex-transitive if its automorphism group acts transitively on vertices of the graph. A vertex-transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this paper, a complete classification is given of tetravalent vertex-transitive non-Cayley graphs of order \(2p^2\) for any prime p.     

一类3p~2阶4度1-正则图

设p为大于3的素数,群G=和H=(其中r(?)1(mod p~2),r~3≡1(mod p~2),3|(p-1))是两类3p~2阶非交换群.通过研究Cayley图的正规性,完成了对G和H的所有4度Cayley图的分类,并得到了一类新的4度1-正则图.     

Morphisms of Ball's Structures of Groups and Graphs

We introduce and study two kinds of morphisms between ball's structures related to groups and graphs.     

Finite structures with prescribed numbers of orbits of their automorphism group

We discuss the problem of existence of finite structures (groups, linear spaces, graphs, ...) with prescribed numbers of orbits of their automorphism groups on the various types of elements. To Dan Hughes for his 80th birthday.