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\-...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.展开更多
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 o...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.展开更多
In this paper, sharp upper bounds for the domination number, total domination number and connected domination number for the Cayley graph G = Cay(D2n, Ω) constructed on the finite dihedral group D2n, and a specified ...In this paper, sharp upper bounds for the domination number, total domination number and connected domination number for the Cayley graph G = Cay(D2n, Ω) constructed on the finite dihedral group D2n, and a specified generating set Ω of D2n. Further efficient dominating sets in G = Cay(D2n, Ω) are also obtained. More specifically, it is proved that some of the proper subgroups of D2n are efficient domination sets. Using this, an E-chain of Cayley graphs on the dihedral group is also constructed.展开更多
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 ...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%.展开更多
Theory of the Cayley graphs is directly linked with the group theory.However,if there are uncertainties on the vertices or edges or both then fuzzy graphs have an extraordinary importance.In this perspective,numbers o...Theory of the Cayley graphs is directly linked with the group theory.However,if there are uncertainties on the vertices or edges or both then fuzzy graphs have an extraordinary importance.In this perspective,numbers of generalηizations of fuzzy graphs have been explored in the literature.Among the others,picture fuzzy graph(PFG)has its own importance.A picture fuzzy graph(PFG)is a pair G=(C,D)defined on a H^(*)=(A,B),where C=(ηC,θ_(C),■_(C))is a picture fuzzy set on A and D=(ηD,θ_(D),■_(D))is a picture fuzzy set over the set B∈A×A such that for any edge mn∈ B with ηD(m,n)≤min(ηC(m),ηC(n)),θD(m,n)≤min(θC(m),θC(n))and ■_(D)(m,n)≥max(■_(C)(m),■_(C)(n)).In this manuscript,we introduce the notion of the Cayley picture fuzzy graphs on groups which is the generalization of the picture fuzzy graphs.Firstly,we discuss few important characteristics of the Cayley picture fuzzy graphs.We show that Cayley picture fuzzy graphs are vertex transitive and hence regular.Then,we investigate different types of Cayley graphs induced by the Cayley picture fuzzy graphs by using different types of cuts.We extensively discuss the term connectivity of the Cayley picture fuzzy graphs.Vertex connectivity and edge connectivity of the Cayley picture fuzzy graphs are also addressed.We also investigate the linkage between these two.Throughout,we provide the extensions of some characηteristics of both the PFGs and Cayley fuzzy graphs in the setting of Cayley picture fuzzy graphs.Finally,we provide the model of interconnected networks based on the Cayley picture fuzzy graphs.展开更多
Let be a connected Cayley graph of group G, then Γ is called normal if the right regular representation of G is a normal subgroup of , the full automorphism group of Γ. For the case where G is a finite nonabelian si...Let be a connected Cayley graph of group G, then Γ is called normal if the right regular representation of G is a normal subgroup of , the full automorphism group of Γ. For the case where G is a finite nonabelian simple group and Γ is symmetric cubic Cayley graph, Caiheng Li and Shangjin Xu proved that Γ is normal with only two exceptions. Since then, the normality of nonsymmetric cubic Cayley graph of nonabelian simple group aroused strong interest of people. So far such graphs which have been known are all normal. Then people conjecture that all of such graphs are either normal or the Cayley subset consists of involutions. In this paper we give an negative answer by two counterexamples. As far as we know these are the first examples for the non-normal cubic nonsymmetric Cayley graphs of finite nonabelian simple groups.展开更多
Since many large graphs are composed from some existing smaller graphs by using graph operations, say, the Cartesian product, the Lexicographic product and the Strong product. Many properties of such large graphs are ...Since many large graphs are composed from some existing smaller graphs by using graph operations, say, the Cartesian product, the Lexicographic product and the Strong product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the Strong product of vertex-transitive graphs. In particular, we show that the Strong product of Cayley graphs is still a Cayley graph.展开更多
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...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.展开更多
We investigate the interaction between a ring R and the Cayley graph Cay(L(R)) of the semigroup of left ideals of R,as well as subdigraphs of this graph. Graph theoretic properties of these graphs are investigated,suc...We investigate the interaction between a ring R and the Cayley graph Cay(L(R)) of the semigroup of left ideals of R,as well as subdigraphs of this graph. Graph theoretic properties of these graphs are investigated,such as transitive closure,girth,radius,diameter,and spanning subgraphs.Conditions on certain of these graphs are given which imply that R is regular,left duo,or that the idempotents of R are central. We characterize simple rings in terms of Cay(L(R)). We characterize strongly regular rings in terms of a subdigraph of Cay(L(R)).展开更多
We call a Cayley digraph X = Cay(G, S) normal for G if the right regular representation of G is normal in the full automorphism group Ant(X) of X. In this paper, we give a classification of all nonnormal Cayley graphs...We call a Cayley digraph X = Cay(G, S) normal for G if the right regular representation of G is normal in the full automorphism group Ant(X) of X. In this paper, we give a classification of all nonnormal Cayley graphs of finite abelian groups with valency 5.展开更多
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（...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.展开更多
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） i...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）.展开更多
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.
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 C...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.展开更多
LetG be a finite group and let S be a nonempty subset of G not containing the identity element 1. The Cayley (di) graph X = Cay(G, S) of G with respect to S is defined byV (X)=G, E (X)={(g,sg)|g∈G, s∈S} A Cayley (di...LetG be a finite group and let S be a nonempty subset of G not containing the identity element 1. The Cayley (di) graph X = Cay(G, S) of G with respect to S is defined byV (X)=G, E (X)={(g,sg)|g∈G, s∈S} A Cayley (di) graph X = Cay (G,S) is said to be normal ifR(G) ?A = Aut (X). A group G is said to have a normal Cayley (di) graph if G has a subset S such that the Cayley (di) graph X = Cay (G, S) is normal. It is proved that every finite group G has a normal Cayley graph unlessG??4×?2 orG?Q 8×? 2 r (r?0) and that every finite group has a normal Cayley digraph, where Zm is the cyclic group of orderm and Q8 is the quaternion group of order 8.展开更多
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 g...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.展开更多
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 ...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.展开更多
文摘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.
文摘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.
文摘In this paper, sharp upper bounds for the domination number, total domination number and connected domination number for the Cayley graph G = Cay(D2n, Ω) constructed on the finite dihedral group D2n, and a specified generating set Ω of D2n. Further efficient dominating sets in G = Cay(D2n, Ω) are also obtained. More specifically, it is proved that some of the proper subgroups of D2n are efficient domination sets. Using this, an E-chain of Cayley graphs on the dihedral group is also constructed.
文摘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%.
文摘Theory of the Cayley graphs is directly linked with the group theory.However,if there are uncertainties on the vertices or edges or both then fuzzy graphs have an extraordinary importance.In this perspective,numbers of generalηizations of fuzzy graphs have been explored in the literature.Among the others,picture fuzzy graph(PFG)has its own importance.A picture fuzzy graph(PFG)is a pair G=(C,D)defined on a H^(*)=(A,B),where C=(ηC,θ_(C),■_(C))is a picture fuzzy set on A and D=(ηD,θ_(D),■_(D))is a picture fuzzy set over the set B∈A×A such that for any edge mn∈ B with ηD(m,n)≤min(ηC(m),ηC(n)),θD(m,n)≤min(θC(m),θC(n))and ■_(D)(m,n)≥max(■_(C)(m),■_(C)(n)).In this manuscript,we introduce the notion of the Cayley picture fuzzy graphs on groups which is the generalization of the picture fuzzy graphs.Firstly,we discuss few important characteristics of the Cayley picture fuzzy graphs.We show that Cayley picture fuzzy graphs are vertex transitive and hence regular.Then,we investigate different types of Cayley graphs induced by the Cayley picture fuzzy graphs by using different types of cuts.We extensively discuss the term connectivity of the Cayley picture fuzzy graphs.Vertex connectivity and edge connectivity of the Cayley picture fuzzy graphs are also addressed.We also investigate the linkage between these two.Throughout,we provide the extensions of some characηteristics of both the PFGs and Cayley fuzzy graphs in the setting of Cayley picture fuzzy graphs.Finally,we provide the model of interconnected networks based on the Cayley picture fuzzy graphs.
文摘Let be a connected Cayley graph of group G, then Γ is called normal if the right regular representation of G is a normal subgroup of , the full automorphism group of Γ. For the case where G is a finite nonabelian simple group and Γ is symmetric cubic Cayley graph, Caiheng Li and Shangjin Xu proved that Γ is normal with only two exceptions. Since then, the normality of nonsymmetric cubic Cayley graph of nonabelian simple group aroused strong interest of people. So far such graphs which have been known are all normal. Then people conjecture that all of such graphs are either normal or the Cayley subset consists of involutions. In this paper we give an negative answer by two counterexamples. As far as we know these are the first examples for the non-normal cubic nonsymmetric Cayley graphs of finite nonabelian simple groups.
基金Supported by the National Natural Science Foundation of China(61164005,11161037,11101232,61440005,11461054)Supported by the Program for Changjiang Scholars and Innovative Research Team in Universities(IRT1068)+1 种基金Supported by the Research Fund for the Chunhui Program of Ministry of Education of China(Z2014022)Supported by the Nature Science Foundation from Qinghai Province(2014-ZJ-721,2014-ZJ-907,2015-ZJ-905)
文摘Since many large graphs are composed from some existing smaller graphs by using graph operations, say, the Cartesian product, the Lexicographic product and the Strong product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the Strong product of vertex-transitive graphs. In particular, we show that the Strong product of Cayley graphs is still a Cayley graph.
文摘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.
文摘We investigate the interaction between a ring R and the Cayley graph Cay(L(R)) of the semigroup of left ideals of R,as well as subdigraphs of this graph. Graph theoretic properties of these graphs are investigated,such as transitive closure,girth,radius,diameter,and spanning subgraphs.Conditions on certain of these graphs are given which imply that R is regular,left duo,or that the idempotents of R are central. We characterize simple rings in terms of Cay(L(R)). We characterize strongly regular rings in terms of a subdigraph of Cay(L(R)).
基金KOSEF Grant 96-0701-03-01-3, and also by the National Natural ScienceFoundation and the Postdoctoral Science Foundation of Chi
文摘We call a Cayley digraph X = Cay(G, S) normal for G if the right regular representation of G is normal in the full automorphism group Ant(X) of X. In this paper, we give a classification of all nonnormal Cayley graphs of finite abelian groups with valency 5.
文摘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.
文摘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）.
文摘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.
基金This work was supported by the NNSFC (Grant No. 10571013)KPCME (Grant No. 106029)SRFDP in China
文摘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.
文摘LetG be a finite group and let S be a nonempty subset of G not containing the identity element 1. The Cayley (di) graph X = Cay(G, S) of G with respect to S is defined byV (X)=G, E (X)={(g,sg)|g∈G, s∈S} A Cayley (di) graph X = Cay (G,S) is said to be normal ifR(G) ?A = Aut (X). A group G is said to have a normal Cayley (di) graph if G has a subset S such that the Cayley (di) graph X = Cay (G, S) is normal. It is proved that every finite group G has a normal Cayley graph unlessG??4×?2 orG?Q 8×? 2 r (r?0) and that every finite group has a normal Cayley digraph, where Zm is the cyclic group of orderm and Q8 is the quaternion group of order 8.
文摘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.
基金This work was supported by the National Natural Science Foundation of China(Grant Nos.19831050 and 10161001)by RFDP(2000000102).
文摘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.
