The diameters of almost all Cayley digraphs

1.IntroductionLetGbeagroupandSasubsetofGnotcontainingtheidentity,1ofG.TheCayleydigraphofGwithrespecttoS,denotedbyX(G,S),isadigraphwhosevertexsetisGandforx,yEG,thereisanarcfromxtoyinX(G,S)ifandonlyifx--laES.IfS=S--',thenX(G,S)isactuallyagraphcalledCayleygraph.ThereisadiversityofliteratureonCnyleygraphsandCayleydigraphs.Themostlyinvestigatedsubjectsaretheconnectivityll'2],theHamiltonianpropertiesl3],theisomorphismsI4]andthediameterIS'6].Recelltly,someauthorsproposedtouseCayleygraph…     

On non‐Hamiltonian circulant digraphs of outdegree three

We construct infinitely many connected, circulant digraphs of outdegree three that have no Hamiltonian circuit. All of our examples have an even number of vertices, and our examples are of two types: either every vertex in the digraph is adjacent to two diametrically opposite vertices, or every vertex is adjacent to the vertex diametrically opposite to itself. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 319–331, 1999     

A family of weakly distance-regular digraphs of girth 2

A family of commutative weakly distance-regular digraphs of girth 2 was classified in [K. Wang, Commutative weakly distance-regular digraphs of girth 2, European J. Combin. 25 (2004) 363-375]. In this paper, we classify this family of digraphs without the assumption of commutativity.     

HAMILTONIAN CYCLES AND DECOMPOSITIONS OFCAYLEY DIGRAPHS OF FINITE ABELIAN GROUPS

In this paper, Hamiltonian cycles and decompositions of Cayley digraphs are investigat-ed. Sufficient conditions are given for these two problems respectively. Furthermore, the conditions are also necesaary for 2-regular Cayley disraphs, In addition, some known results about theCartesian products of two directed cycles are also deduced.     

Cayley digraphs and lexicographic product

In this paper, we prove that a Cayley digraph Γ = Cay(G, S) is a nontrivial lexicographical product if and only if there is a nontrivial subgroup H of G such that S∖H is a union of some double cosets of H in G.      

On polynomial digraphs

Let Φ(x,y) be a bivariate polynomial with complex coefficients. The zeroes of Φ(x,y) are given a combinatorial structure by considering them as arcs of a directed graph G(Φ). This paper studies some relationship between the polynomial Φ(x,y) and the structure of G(Φ).     

De Bruijn digraphs and affine transformations

Let be the additive group of 1×n row vectors over . For an n×n matrix T over  and , the affine transformation F_T,ω of sends x to xT+ω. Let α be the cyclic group generated by a vector . The affine transformation coset pseudo-digraph has the set of cosets of α in as vertices and there are c arcs from x+α to y+α if and only if the number of zx+α such that F_T,ω(z)y+α is c. We prove that the following statements are equivalent: (a)  is isomorphic to the d-nary (n−1)-dimensional De Bruijn digraph; (b) α is a cyclic vector for T; (c)  is primitive. This strengthens a result conjectured by C.M. Fiduccia and E.M. Jacobson [Universal multistage networks via linear permutations, in: Proceedings of the 1991 ACM/IEEE Conference on Supercomputing, ACM Press, New York, 1991, pp. 380–389]. Under the further assumption that T is invertible we show that each component of is a conjunction of a cycle and a De Bruijn digraph, namely a generalized wrapped butterfly. Finally, we discuss the affine TCP digraph representations for a class of digraphs introduced by D. Coudert, A. Ferreira and S. Perennes [Isomorphisms of the De Bruijn digraph and free-space optical networks, Networks 40 (2002) 155–164].     

Spanning 2-strong tournaments in 3-strong semicomplete digraphs

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph on 2k vertices contains a spanning k-strong tournament.     

Further results on the enumeration of hamilton paths in Cayley digraphs on semidirect products of cyclic groups

First, let m and n be positive integers such that n is odd and gcd(m,n)=1. Let G be the semidirect product of cyclic groups given by . Then the number of hamilton paths in Cay(G:x,y) (with initial vertex 1) is one fewer than the number of visible lattice points that lie on the closed quadrilateral whose vertices in consecutive order are (0,0), (4mn²+2n,16m²n), (n,4m), and (0,8m). Second, let m and n be positive integers such that n is odd. Let G be the semidirect product of cyclic groups given by . Then the number of hamilton paths in Cay(G:x,y) (with initial vertex 1) is (3m-1)n+m⌊(n+1)/3⌋+1.     

Cayley digraphs with normal adjacency matrices

In this paper we give a criterion for the adjacency matrix of a Cayley digraph to be normal in terms of the Cayley subset S. It is shown with the use of this result that the adjacency matrix of every Cayley digraph on a finite group G is normal iff G is either abelian or has the form for some non-negative integer n, where Q₈ is the quaternion group and is the abelian group of order 2ⁿ and exponent 2.     

一类非正规Cayley有向图

本文研究了2p2(p奇素数)阶非交换群上两度Cayley有向图的正规性,发现 了一无限族非正规的Cayley有向图.     

A Family of Nonnormal Cayley Digraphs

We call a Cayley digraph Γ = Cay(G, S) normal for G if G _R , the right regular representation of G, is a normal subgroup of the full automorphism group Aut(Γ) of Γ. In this paper we determine the normality of Cayley digraphs of valency 2 on nonabelian groups of order 2p ² (p odd prime). As a result, a family of nonnormal Cayley digraphs is found. Received February 23, 1998, Revised September 25, 1998, Accepted October 27, 1998     

On the Normality of Cayley Digraphs of Valency 2 on Non-Abelian Group of Odd Order

In this paper, we prove that the Cayley digraph = Cay(G, S) of valency 2 on non-abelian group G of odd order is normal if the automorphism group of A(), a graph constructed from by using the method presented in the paper, is primitive on the vertices set V(A(). We also prove that the Cayley digraphs of valency 2 on non-abelian group of order pq² are normal, where p and q are distinct odd primes.AMS Subject Classification (2000) 05C25 20B25Supported by the National Natural Science Foundation of China (Grant no. 19971086) and the Doctoral Program Foundation of the National Education Department of China.     

On large vertex-symmetric digraphs

There is special interest in the design of large vertex-symmetric graphs and digraphs as models of interconnection networks for implementing parallelism. In these systems, a large number of nodes are connected with relatively few links and short paths between the nodes, and each node may execute the same communication software without modifications.In this paper, a method for obtaining new general families of large vertex-symmetric digraphs is put forward. To be more precise, from a k-reachable vertex-symmetric digraph and another (k+1)-reachable digraph related to the previous one, and using a new special composition of digraphs, new families of vertex-symmetric digraphs with small diameter are presented. With these families we obtain new vertex-symmetric digraphs that improve various values of the table of the largest known vertex-symmetric (Δ,D)-digraphs. The paper also contains the (Δ,D)-table for vertex-symmetric digraphs, for Δ≤13 and D≤12.     

Kernels in quasi-transitive digraphs

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.A kernel N of D is an independent set of vertices such that for every w∈V(D)-N there exists an arc from w to N. A digraph is called quasi-transitive when (u,v)∈A(D) and (v,w)∈A(D) implies (u,w)∈A(D) or (w,u)∈A(D). This concept was introduced by Ghouilá-Houri [Caractérisation des graphes non orientés dont on peut orienter les arrêtes de maniere à obtenir le graphe d’ un relation d’ordre, C.R. Acad. Sci. Paris 254 (1962) 1370-1371] and has been studied by several authors. In this paper the following result is proved: Let D be a digraph. Suppose D=D₁∪D₂ where D_i is a quasi-transitive digraph which contains no asymmetrical infinite outward path (in D_i) for i∈{1,2}; and that every directed cycle of length 3 contained in D has at least two symmetrical arcs, then D has a kernel. All the conditions for the theorem are tight.     

6p阶2度有向Cayley图的正规性

群G的Cayley有向图X=Cay(G,S)叫做正规的,如果G的右正则表示R(G)在X的全自同构群Aut(X)中正规.决定了6p(p素数)阶2度有向Cayley图的正规性,发现了一个新的2度非正规Cayley有向图.     

Weakly distance-regular digraphs

We introduce the concept of weakly distance-regular digraph and study some of its basic properties. In particular, the (standard) distance-regular digraphs, introduced by Damerell, turn out to be those weakly distance-regular digraphs which have a normal adjacency matrix. As happens in the case of distance-regular graphs, the study is greatly facilitated by a family of orthogonal polynomials called the distance polynomials. For instance, these polynomials are used to derive the spectrum of a weakly distance-regular digraph. Some examples of these digraphs, such as the butterfly and the cycle prefix digraph which are interesting for their applications, are analyzed in the light of the developed theory. Also, some new constructions involving the line digraph and other techniques are presented.     

Gaussian integral circulant digraphs

The spectrum of a digraph in general contains real and complex eigenvalues. A digraph is called a Gaussian integral digraph if it has a Gaussian integral spectrum that is all eigenvalues are Gaussian integers. In this paper, we consider Gaussian integral digraphs among circulant digraphs.