Continuous-Time Classical and Quantum Random Walk on Direct Product of Cayley Graphs

In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph is obtained by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determining probability of walk on compficated graphs. Using this method, we calculate the probability of Continuous-time classical and quantum random walks on many of finite direct product Cayley graphs （complete cycle, complete Kn, charter and n-cube）. Also, we inquire that the classical state the stationary uniform distribution is reached as t→∞ but for quantum state is not always satisfied.

Small-World Networks with Unitary Cayley Graphs for Various Energy Generation

Complex networks have been a prominent topic of research for several years,spanning a wide range of fields from mathematics to computer science and also to social and biological sciences.The eigenvalues of the Seidel matrix,Seidel Signless Laplacian matrix,Seidel energy,Seidel Signless Laplacian energy,Maximum and Minimum energy,Degree Sum energy and Distance Degree energy of the Unitary Cayley graphs[UCG]have been calculated.Low-power devices must be able to transfer data across long distances with low delay and reliability.To overcome this drawback a small-world network depending on the unitary Cayley graph is proposed to decrease the delay and increase the reliability and is also used to create and analyze network communication.Small-world networks based on the Cayley graph have a basic construction and are highly adaptable.The simulation result shows that the small-world network based on unitary Cayley graphs has a shorter delay and is more reliable.Furthermore,the maximum delay is lowered by 40%.

A CLASS OF HAMILTONIAN AND EDGE SYMMETRIC CAYLEY GRAPHS ON SYMMETRIC GROUPS

Let S\-n be the symmetric group, g\++\-i=(123i),g\+-\-i=(1i32) and M\++\-n={g\++\-i∶4≤i≤n}, then M\++\-n is a minimal generating set of S\-n ,where n ≥5.It is proved that Cayley graph Cay( S\-n,M\++\-n∪M\+-\-n) is Hamiltonian and edge symmetric.

Normal edge-transitive Cayley graphs on a class of non-abelian groups

Let Г=Cay(G,S)be the Cayley graph of a group G with respect to its subset S.The graph is said to be normal edge-transitive if the normalizer of G in the automorphism group Aut(T)of F acts transitively on the edge set of ГIn this paper,we study the structure of normal edge-transitive Cayley graphs on a class of non-abelian groups with order 2p^(2)(p refers to an odd prime).The structure and automorphism groups of the non-abelian groups are first presented,and then the tetravalent normal edge-transitive Cayley graphs on such groups are investigated.Finally,the normal edge-transitive Cayley graphs on group G are characterized and classified.

AUTOMORPHISM GROUPS OF 4-VALENT CONNECTED CAYLEY GRAPHS OF p-GROUPS

Let G be a p-group (p odd prime) and let X = Cay(G, S) be a 4-valent connected Cayley graph. It is shown that if G has nilpotent class 2, then the automorphism group Ant(X) of X is isomorphic to the semidirect product GR x Ant(G,S), where GR is the right regular representation of G and Aut(G,S) is the subgroup of the automorphism group Aut(G) of G which fixes S setwise. However the result is not true if G has nilpotent class 3 and this paper provides a counterexample.

Spectra of Generalized Cayley Graphs on Finite Abelian Groups

The spectra of generalized Cayley graphs of finite abelian groups are investigated in this paper.For a generalized Cayley graph X of a finite group G,the canonical double covering of X is the direct product X×K_(2).In this paper,integral generalized Cayley graphs on finite abelian groups are characterized,using the characterization of the spectra of integral Cayley graphs.As an application,the integral generalized Cayley graphs on Z_(p)×Z_(q) and Z2n are investigated,where p and q are odd prime numbers.

Finite locally primitive abelian Cayley graphs

Let Γ be a finite connected locally primitive Cayley graph of an abelian group.It is shown that one of the following holds:(1) Γ = Kn,Kn,n,Kn,n-nK2,Kn ×···× Kn;(2) Γ is the standard double cover of Kn ×···× Kn ;(3) Γ is a normal or a bi-normal Cayley graph of an elementary abelian or a meta-abelian 2-group.

Neighbor Connectivity of Two Kinds of Cayley Graphs

In this paper, we determine the neighbor connectivity κNB of two kinds of Cayley graphs： alter- nating group networks ANn and star graphs Sn; and give the exact values of edge neighbor connectivity λNB of ANn and Cayley graphs generated by transposition trees Fn. Those are κNB（ANn） = n-1, λNB（ANn） = n-2 and κNB（Sn） = λNB（Гn） = n - 1.

On the Panfactorical Property of Cayley Graphs

A κ-regular graph is called panfactorical, or even panfactorical respectively, if for every integer s, 1 ≤ s ≤ κ,there exists an s-factor, or 2[s/2 ]-factor, in this graph. A criterion for checking an γ-regular graph to be panfactorical or even panfactorical is established. It is proved that every Cayley graph of odd degree is panfactorical and every Cayley graph of even degree is even panfactorical by using this criterion. For a dihedral group, we prove that every connected Cayley graph on this group is panfactorial.

Cubic vertex-transitive non-Cayley graphs of order 12p

A graph is said to be vertex-transitive non-Cayley if its full automorphism group acts transitively on its vertices and contains no subgroups acting regularly on its vertices. In this paper, a complete classification of cubic vertex-transitive non-Cayley graphs of order 12 p, where p is a prime, is given. As a result, there are 11 sporadic and one infinite family of such graphs, of which the sporadic ones occur when p equals 5, 7 or 17, and the infinite family exists if and only if p ≡ 1(mod 4), and in this family there is a unique graph for a given order.

One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.

Normal edge-transitive Cayley graphs on non-abelian groups of order 4p,where p is a prime number

We determine all connected normal edge-transitive Cayley graphs on non-abelian groups with order 4p, where p is a prime number. As a consequence we prove if IGI = 25p, δ = 0, 1, 2 and p prime, then F 1 Cay（G, S） is a connected normal 1/2 arc-transitive Cayley graph only if G = F4p, where S is an inverse closed generating subset of G which does not contain the identity element of G and F4p is a group with presentation F4p = （a, b ｜aP = b4 = 1, b-lab = a^λ）, where λ2 = -1 （mod p）.

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.

Two sufficient conditions for non-normal Cayley graphs and their applications

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 the full automorphism group of Cay(G, S). In this paper, two sufficient conditions for non-normal Cayley graphs are given and by using the conditions, five infinite families of connected non-normal Cayley graphs are constructed. As an application, all connected non-normal Cayley graphs of valency 5 on A 5 are determined, which generalizes a result about the normality of Cayley graphs of valency 3 or 4 on A 5 determined by Xu and Xu. Further, we classify all non-CI Cayley graphs of valency 5 on A 5, while Xu et al. have proved that A 5 is a 4-CI group.

Enumeration of Cubic Cayley Graphs on Dihedral Groups

Let p be an odd prime, and D2p = （a,b I aP = b2 = l,bab= a 1） the dihedral group of order 2p. In this paper, we completely classify the cubic Cayley graphs on D2p up to isomorphism by means of spectral method. By the way, we show that two cubic Cayley graphs on D2p are isomorphic if and only if they are cospectral. Moreover, we obtain the number of isomorphic classes of cubic Cayley graphs on D2 by using Gauss＇ celebrated law of quadratic reciprocity.

Connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups

A graph is said to be s-arc-regular if its full automorphism group acts regularly on the set of its s-arcs. In this paper, we investigate connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups. Two sufficient and necessary conditions for such graphs to be 1- or 2-arcregular are given and based on the conditions, several infinite families of 1- or 2-arc-regular cubic Cayley graphs of alternating groups are constructed.

Locally primitive Cayley graphs of finite simple groups

A graph Г is said to be G-locally primitive, where G is a subgroup of automorphisms of Г, if the stabiliser Ga of a vertex α acts primitively on the set Г( α ) of vertices of Г adjacent to α. For a finite non-abelian simple group L and a Cayley subset S of L, suppose that L ? G ? Aut( L), and the Cayley graph Г = Cay ( L, S) is G-locally primitive. In this paper we prove that L is a simple group of Lie type, and either the valency of Г is an add prine divisor of |Out(L)|, orL =PΩ 8 + (q) and Г has valency 4. In either cases, it is proved that the full automorphism group of Г is also almost simple with the same socle L.

Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we show that this conjecture is true for Cayley graph on generalized dihedral groups and generalized quaternion groups, which generalizes the result of F. Yang and X. Li [Inform. Process. Lett., 2011, 111： 416-419]. We also generalizes an early result of M. Nanasiova and M. Skoviera [J. Algebraic Combin., 2009, 30： 103-110].

Integral Cayley Graphs over Finite Groups

We prove that the spectrum of a Cayley graph over a finite group with a normal generating set S containing with every its element s all generators of the cyclic group(s)is integral.In particular,a Cayley graph of a 2-group generated by a normal set of involutions is integral.We prove that a Cayley graph over the symmetric group of degree n no less than 2 generated by all transpositions is integral.We find the spectrum of a Cayley graph over the alternating group of degree n no less than 4 with a generating set of 3-cycles of the form(k i j)with fixed k,a s{-n+1,1-n+1,2^2-n+1,...,(n-1)2-n+1}.

Isomorphisms of Finite Semi-Cayley Graphs

Let G be a finite group. A Cayley graph over G is a simple graph whose automorphism group has a regular subgroup isomorphic to G. A Cayley graph is called a CI-graph （Cayley iso- morphism） if its isomorphic images are induced by automorphisms of G. A well-known result of Babai states that a Cayley graph F of G is a CI-graph if and only if all regular subgroups of Aut（F） isomorphic to G are conjugate in Aut（F）. A semi-Cayley graph （also called bi-Cayley graph by some authors） over G is a simple graph whose automorphism group has a semiregular subgroup isomorphic to G with two orbits （of equal size）. In this paper, we introduce the concept of SCI-graph （semi-Cayley isomorphism） and prove a Babai type theorem for semi-Cayley graphs. We prove that every semi-Cayley graph of a finite group G is an SCI-graph if and only if G is cyclic of order 3. Also, we study the isomorphism problem of a special class of semi-Cayley graphs.