A construction of an infinite family of 2-arc transitive polygonal graphs of arbitrary odd girth

A near-polygonal graph is a graph Γ which has a set C of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C. If m is the girth of Γ then the graph is called polygonal. We provide a construction of an infinite family of polygonal graphs of arbitrary odd girth with 2-arc transitive automorphism groups.     

The locally 2-arc transitive graphs admitting an almost simple group of Suzuki type

In this paper, seven families of vertex-intransitive locally (G,2)-arc transitive graphs are constructed, where Sz(q)?G?Aut(Sz(q)), q=²2k+1 for some k∈N. It is then shown that for any graph Γ in one of these families, Sz(q)?Aut(Γ)?Aut(Sz(q)) and that the only locally 2-arc transitive graphs admitting an almost simple group of Suzuki type whose vertices all have valency at least three are (i) graphs in these seven families, (ii) (vertex transitive) 2-arc transitive graphs admitting an almost simple group of Suzuki type, or (iii) double covers of the graphs in (ii). Since the graphs in (ii) have been classified by Fang and Praeger (1999) [6], this completes the classification of locally 2-arc transitive graphs admitting a Suzuki simple group     

A note on the girth‐doubling construction for polygonal graphs

A near‐polygonal graph is a graph Γ which has a set ?? of m‐cycles for some positive integer m such that each 2‐path of Γ is contained in exactly one cycle in ??. If m is the girth of Γ then the graph is called polygonal. Given a polygonal graph Γ of valency r and girth m, Archdeacon and Perkel proved the existence of a polygonal graph Γ₂ of valency r and girth 2m. We will show that this construction can be extended to one that yields a polygonal graph Γ₃ of valency r and girth 3m, but that making the cycles any longer with this construction does not yield a polygonal graph. We also show that if Aut(Γ) is 2‐arc transitive, so is Aut(Γ_k) for k = 2, 3. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 246‐254, 2011     

On automorphism groups of quasiprimitive 2-arc transitive graphs

We characterize the automorphism groups of quasiprimitive 2-arc-transitive graphs of twisted wreath product type. This is a partial solution for a problem of Praeger regarding quasiprimitive 2-arc transitive graphs. The solution stimulates several further research problems regarding automorphism groups of edge-transitive Cayley graphs and digraphs. This work forms part of an ARC grant project and is supported by a QEII Fellowship.     

Orthogonal graphs of odd characteristic and their automorphisms

The (isotropic) orthogonal graph O(2ν+δ,q) over of odd characteristic, where ν1 and δ=0,1 or 2 is introduced. When ν=1, O(21+δ,q) is a complete graph. When ν2, O(2ν+δ,q) is strongly regular and its parameters are computed, as well as its chromatic number. The automorphism groups of orthogonal graphs are also determined.     

kpm阶2-弧传递图

2-弧传递图是对称图类的一个重要的子类,而拟本原和双拟本原的2-弧传递图在2-弧传递图的研究中具有最基本的意义．文中对阶为kp^m（k,p是素数,k≠p,m≥2是整数)的基本2-孤传递图进行了研究。获得了下列结果：(1)kp^m阶G-拟本原的2-弧传递图是几乎单的．(2)对2p^m阶和2^mk阶双拟本原的2-弧传递图的分类进行了刻划,确定了其自同构群的基柱．     

Finite vertex primitive 2-arc regular graphs

A classification is given of finite graphs that are vertex primitive and 2-arc regular. The classification involves various new constructions of interesting 2-arc transitive graphs.     

On the computational complexity of partial covers of Theta graphs

By use of elementary geometric arguments we prove the existence of a special integral solution of a certain system of linear equations. The existence of such a solution then yields the NP-hardness of the decision problem on the existence of locally injective homomorphisms to Theta graphs with three distinct odd path lengths.     

CLASSIFICATION OF PRIMITIVE （J1,2）-ARC TRANSITIVE GRAPHS

In the author＇s Ph. D thesis, a non-quasiprimitive graph admitting a quasiprimitive automorphism group isomorphic to J1 was constructed ,where J1 is Janko simple group of order 175560. Is this the only one for J1？ In this paper all primitive （J1,2）-arc transitive graphs Г are given and that AutГ≌J1 is proved.     

Planarity of Cayley graphs of graph products of groups

We obtain a complete classification of graph products of finite abelian groups whose Cayley graphs with respect to the standard presentations are planar.     

s‐Regular cubic graphs as coverings of the complete bipartite graph K3,3

A graph is s‐regular if its automorphism group acts freely and transitively on the set of s‐arcs. An infinite family of cubic 1‐regular graphs was constructed in [10], as cyclic coverings of the three‐dimensional Hypercube. In this paper, we classify the s‐regular cyclic coverings of the complete bipartite graph K_3,3 for each ≥ 1 whose fibre‐preserving automorphism subgroups act arc‐transitively. As a result, a new infinite family of cubic 1‐regular graphs is constructed. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 101–112, 2004     

A new family of Geodesic transitive graphs

We present a new family of locally geodesic transitive graphs with arbitrarily large diameter and valencies, containing a particular case to be geodesic transitive. We also prove that it is a unique family in some generalised family of graphs.     

Automorphism Group of the Rank-decreasing Graph Over the Semigroup of Upper Triangular Matrices

Let F_q be a finite field with q elements, n ≥ 2 a positive integer, and T(n, q) the semigroup of all n × n upper triangular matrices over F_q. The rank-decreasing graph 𝕋 of T(n, q) is a directed graph which has T(n, q) as vertex set, and there is a directed edge from A ∈ T(n, q) to B ∈ T(n, q) if and only if r(AB) < r(B). The zero-divisor graph 𝒯 of T(n, q), with vertex set of all nonzero zero-divisors of T(n, q) and there is a directed edge from a vertex A to a vertex B if and only if AB = 0, can be viewed as a subgraph of 𝕋. In [16 Wang, L. (2015). A note on automorphisms of the zero-divisor graph of upper triangular matrices. Lin. Alg. Appl. 465:214–220.[Crossref], [Web of Science ®] , [Google Scholar]], L. Wang has determined the automorphisms of the zero-divisor graph 𝒯 of T(n, q). In this article, by applying the main result of [17 Wong, D., Ma, X., Zhou, J. (2014). The group of automorphisms of a zero-divisor graph based on rank one upper triangular matrices. Lin. Alg. Appl. 460:242–258.[Crossref], [Web of Science ®] , [Google Scholar]] we determine the automorphisms of the rank-decreasing graph 𝕋 of T(n, q).     

Locally s‐distance transitive graphs

We give a unified approach to analyzing, for each positive integer s, a class of finite connected graphs that contains all the distance transitive graphs as well as the locally s‐arc transitive graphs of diameter at least s. A graph is in the class if it is connected and if, for each vertex v, the subgroup of automorphisms fixing v acts transitively on the set of vertices at distance i from v, for each i from 1 to s. We prove that this class is closed under forming normal quotients. Several graphs in the class are designated as degenerate, and a nondegenerate graph in the class is called basic if all its nontrivial normal quotients are degenerate. We prove that, for s≥2, a nondegenerate, nonbasic graph in the class is either a complete multipartite graph or a normal cover of a basic graph. We prove further that, apart from the complete bipartite graphs, each basic graph admits a faithful quasiprimitive action on each of its (1 or 2) vertex‐orbits or a biquasiprimitive action. These results invite detailed additional analysis of the basic graphs using the theory of quasiprimitive permutation groups. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:176‐197, 2012     

Uncountable families of vertex-transitive graphs of finite degree

We prove that the set of vertex-transitive graphs of finite degree is uncountably large.     

A characterization of block graphs

A block graph is a graph whose blocks are cliques. For each edge e=uv of a graph G, let N_e(u) denote the set of all vertices in G which are closer to u than v. In this paper we prove that a graph G is a block graph if and only if it satisfies two conditions: (a) The shortest path between any two vertices of G is unique; and (b) For each edge e=uv∈E(G), if x∈N_e(u) and y∈N_e(v), then, and only then, the shortest path between x and y contains the edge e. This confirms a conjecture of Dobrynin and Gutman [A.A. Dobrynin, I. Gutman, On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math., Beograd. 56 (1994) 18-22].     

Cyclic orthogonal double covers of 4-regular circulant graphs

An orthogonal double cover (ODC) of a graph H is a collection G={G_v:v∈V(H)} of |V(H)| subgraphs of H such that every edge of H is contained in exactly two members of G and for any two members G_u and G_v in G, |E(G_u)∩E(G_v)| is 1 if u and v are adjacent in H and it is 0 if u and v are nonadjacent in H. An ODC G of H is cyclic (CODC) if the cyclic group of order |V(H)| is a subgroup of the automorphism group of G. In this paper, we are concerned with CODCs of 4-regular circulant graphs.