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%.展开更多
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.展开更多
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_(...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.展开更多
We show that,up to isomorphism,there is a unique non-CI connected cubic Cayley graph on the dihedral group of order 2n for each even number n≥4.This answers in the negative the question of Li whether all connected cu...We show that,up to isomorphism,there is a unique non-CI connected cubic Cayley graph on the dihedral group of order 2n for each even number n≥4.This answers in the negative the question of Li whether all connected cubic Cayley graphs are CI-graphs(Discrete Math.,256,301-334(2002)).As an application,a formula is derived for the number of isomorphism classes of connected cubic Cayley graphs on dihedral groups,which generalises the earlier formula of Huang et al.dealing with the particular case when n is a prime(Acta Math.Sin.,Engl.Ser.,33,996-1011(2017)).As another application,a short proof is also given for a result on sparse circulant matrices obtained by Wiedemann and Zieve(arXiv preprint,(2007)).展开更多
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.展开更多
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 C...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.展开更多
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.展开更多
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.
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 th...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.展开更多
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, ...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].展开更多
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-...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}.展开更多
In this paper we determine all tetravalent Cayley graphs of a non-abelian group of order 3p2, where p is a prime number greater than 3, and with a cyclic Sylow p-subgroup. We show that all of these tetravalent Cayley ...In this paper we determine all tetravalent Cayley graphs of a non-abelian group of order 3p2, where p is a prime number greater than 3, and with a cyclic Sylow p-subgroup. We show that all of these tetravalent Cayley graphs are normal. The full automorphism group of these Cayley graphs is given and the half-transitivity and the arc-transitivity of these graphs are investigated. We show that this group is a 5-CI-group.展开更多
In a connected graph G, the distance d(u, v) denotes the distance between two vertices u and v of G. Let W = {w1, w2,……, wk} be an ordered set of vertices of G and let v be a vertex of G. The representation r(v1W...In a connected graph G, the distance d(u, v) denotes the distance between two vertices u and v of G. Let W = {w1, w2,……, wk} be an ordered set of vertices of G and let v be a vertex of G. The representation r(v1W) of v with respect to W is the k-tuple (d(v, w1), d(v, w2),…, d(v, wk)). The set W is called a resolving set or a locating set if every vertex of G is uniquely identified by its distances from the vertices of W, or equivalently, if distinct vertices of G have distinct representations with respect to W. A resolving set of minimum cardinality is called a metric basis for G and this cardinality is the metric dimension of G, denoted by β(G). Metric dimension is a generalization of affine dimension to arbitrary metric spaces (provided a resolving set exists). In this paper, we study the metric dimension of barycentric subdivision of Cayley graphs Cay (Zn Z2). We prove that these subdivisions of Cayley graphs have constant metric dimension and only three vertices chosen appropriately suffice to resolve all the vertices of barycentric subdivision of Cayley graphs Cay (Zn Z2).展开更多
Recently,there are extensive studies on perfect state transfer(PST for short)on graphs due to their significant applications in quantum information processing and quantum computations.However,there is not any general ...Recently,there are extensive studies on perfect state transfer(PST for short)on graphs due to their significant applications in quantum information processing and quantum computations.However,there is not any general characterization of graphs that have PST in literature.In this paper,the authors present a depiction on weighted abelian Cayley graphs having PST.They give a unified approach to describe the periodicity and the existence of PST on some specific graphs.展开更多
Cayley graphs have many good properties as models of communication networks. This study analyzes the reliability of the Cayley graph based on the dihedral graph. Graph theory and analyses show that almost all Cayley g...Cayley graphs have many good properties as models of communication networks. This study analyzes the reliability of the Cayley graph based on the dihedral graph. Graph theory and analyses show that almost all Cayley graphs of the dihedral graph D2n are optimal super-λ. The number Ni(G) of cutsets of size i, λ≤ i≤λ' is given as Ni(G) = n[^(n-1)δ i-δ].展开更多
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 a...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.展开更多
t Let F = Cay(G, S), R(G) be the right regular representation of G. The graph Г is called normal with respect to G, if R(G) is normal in the full automorphism group Aut(F) of F. Г is called a bi-normal with ...t Let F = Cay(G, S), R(G) be the right regular representation of G. The graph Г is called normal with respect to G, if R(G) is normal in the full automorphism group Aut(F) of F. Г is called a bi-normal with respect to G if R(G) is not normal in Aut(Г), but R(G) contains a subgroup of index 2 which is normal in Aut(F). In this paper, we prove that connected tetravalent edge-transitive Cayley graphs on PGL(2,p) are either normal or bi-normal when p ≠ 11 is a prime.展开更多
Let R be a commutative ring and U(R)the multiplicative group of unit elements of R.In 2012,Khashyarmanesh et al.defined the generalized unit and unitary Cayley graph,T(R,G,S),corresponding to a multiplicative subgroup...Let R be a commutative ring and U(R)the multiplicative group of unit elements of R.In 2012,Khashyarmanesh et al.defined the generalized unit and unitary Cayley graph,T(R,G,S),corresponding to a multiplicative subgroup G of U(R)and a nonempty subset S of G with S^(-1)={s^(-1)|s∈S}■S,asthegraphwithvertexsetR and two distinct vertices x and y being adjacent if and only if there exists s∈S such that x+sy∈G.In this paper,we characterize all Artinian rings R for which T(R,U(R),S)is projective.This leads us to determine all Artinian rings whose unit graphs,unitary Cayley graphs and co-maximal graphs are projective.In addition,we prove that for an Artinian ring R for which T(R,U(R),S)has finite nonorientable genus,R must be a finite ring.Finally,it is proved that for a given positive integer k,the number of finite rings R for which T(R,U(R),S)has nonorientable genus k is finite.展开更多
Let Sn denote the symmetric group of degree n with n 〉 3, S = {cn = (1 2…n), cn^-1, (1 2)} and Fn=Cay(Sn, S) be the Cayley graph on Sn with respect to S. In this paper, we show that Fn (n 〉 13) is a normal ...Let Sn denote the symmetric group of degree n with n 〉 3, S = {cn = (1 2…n), cn^-1, (1 2)} and Fn=Cay(Sn, S) be the Cayley graph on Sn with respect to S. In this paper, we show that Fn (n 〉 13) is a normal Cayley graph, and that the full automorphism group of Fn is equal to Aut(Гn) = R(Sn) (Inn(C))≌- Sn×Z2, where R(Sn) is the right regular representation of Sn,φ = (1 2)(3 n)(4 n-1)(5 n-2)... (∈ Sn), and Inn(C) is the inner isomorphism of Sn induced by φ .展开更多
A Cayley graph Г=Cay(G,S)is said to be normal if G is normal in Aut Г.In this paper,we investigate the normality problem of the connected 11-valent symmetric Cayley graphs Г of finite nonabelian simple groups G,whe...A Cayley graph Г=Cay(G,S)is said to be normal if G is normal in Aut Г.In this paper,we investigate the normality problem of the connected 11-valent symmetric Cayley graphs Г of finite nonabelian simple groups G,where the vertex stabilizer A_(u) is soluble for A=Aut Г and v∈∨Г.We prove that either Г is normal or G=A_(5),A_(10),A_(54),A_(274),A_(549) or A_(1099).Further,11-valent symmetric nonnormal Cayley graphs of As,A54 and A274 are constructed.This provides some more examples of nonnormal 11-valent symmetric Cayley graphs of finite nonabelian simple groups after the first graph of this kind(of valency 11)was constructed by Fang,Ma and Wang in 2011.展开更多
文摘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%.
文摘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.
基金supported by the National Natural Science Foundation of China(No.12271311,12101410,12201414)Taishan Scholars Program of Shandong Province.
文摘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.
基金Supported by the Slovenian Research Agency (research program P1-0285 and research projects N1-0062,J1-9108,J1-1695,N1-0140,J1-2451,N1-0208 and J1-3001)。
文摘We show that,up to isomorphism,there is a unique non-CI connected cubic Cayley graph on the dihedral group of order 2n for each even number n≥4.This answers in the negative the question of Li whether all connected cubic Cayley graphs are CI-graphs(Discrete Math.,256,301-334(2002)).As an application,a formula is derived for the number of isomorphism classes of connected cubic Cayley graphs on dihedral groups,which generalises the earlier formula of Huang et al.dealing with the particular case when n is a prime(Acta Math.Sin.,Engl.Ser.,33,996-1011(2017)).As another application,a short proof is also given for a result on sparse circulant matrices obtained by Wiedemann and Zieve(arXiv preprint,(2007)).
文摘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.
基金Supported by the National Natural Science Foundation of China(No.11371052,11731002,11571035)
文摘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.
文摘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.
文摘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.
基金Supported by National Natural Science Foundation of China(Grant Nos.11671344 and 11531011)
文摘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.
基金Acknowledgements The first author was supported by the Natural Science Foundation of China (Grant No. 11301254), the Natural Science Foundation of Henan Province (Grant No. 132300410313), and the Natural Science Foundation of Education Bureau of Henan Province (Grant No. 13A110800). The second author was supported by the National Natural Science Foundation of China (Grant No. 11171129) and the Doctoral Fund of Ministry of Education of China (Grant No. 20130144110001).
文摘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].
基金The work was supported by the Program of Fundamental Scientific Research of the SB RAS N 1.5.1,project No.0314-2019-0016.
文摘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}.
文摘In this paper we determine all tetravalent Cayley graphs of a non-abelian group of order 3p2, where p is a prime number greater than 3, and with a cyclic Sylow p-subgroup. We show that all of these tetravalent Cayley graphs are normal. The full automorphism group of these Cayley graphs is given and the half-transitivity and the arc-transitivity of these graphs are investigated. We show that this group is a 5-CI-group.
基金Supported by the National University of Sciences and Technology(NUST),H-12,Islamabad,Pakistan
文摘In a connected graph G, the distance d(u, v) denotes the distance between two vertices u and v of G. Let W = {w1, w2,……, wk} be an ordered set of vertices of G and let v be a vertex of G. The representation r(v1W) of v with respect to W is the k-tuple (d(v, w1), d(v, w2),…, d(v, wk)). The set W is called a resolving set or a locating set if every vertex of G is uniquely identified by its distances from the vertices of W, or equivalently, if distinct vertices of G have distinct representations with respect to W. A resolving set of minimum cardinality is called a metric basis for G and this cardinality is the metric dimension of G, denoted by β(G). Metric dimension is a generalization of affine dimension to arbitrary metric spaces (provided a resolving set exists). In this paper, we study the metric dimension of barycentric subdivision of Cayley graphs Cay (Zn Z2). We prove that these subdivisions of Cayley graphs have constant metric dimension and only three vertices chosen appropriately suffice to resolve all the vertices of barycentric subdivision of Cayley graphs Cay (Zn Z2).
基金supported by the National Natural Science Foundation of China(Nos.11771007,11601003,11801007,12031011)Natural Science Foundation of Anhui Province(No.1808085MA17)。
文摘Recently,there are extensive studies on perfect state transfer(PST for short)on graphs due to their significant applications in quantum information processing and quantum computations.However,there is not any general characterization of graphs that have PST in literature.In this paper,the authors present a depiction on weighted abelian Cayley graphs having PST.They give a unified approach to describe the periodicity and the existence of PST on some specific graphs.
基金Supported by the National Key Basic Research and Development (973) Program of China(No. 2007CB311003)
文摘Cayley graphs have many good properties as models of communication networks. This study analyzes the reliability of the Cayley graph based on the dihedral graph. Graph theory and analyses show that almost all Cayley graphs of the dihedral graph D2n are optimal super-λ. The number Ni(G) of cutsets of size i, λ≤ i≤λ' is given as Ni(G) = n[^(n-1)δ i-δ].
文摘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.
基金Supported by the National Natural Science Foundation of China(No.11171020,10961004)the Henan Province Foundation and Frontier Technology Research Plan(No.112300410205)+1 种基金the Education Department of Henan Science and Technology Research Key Project(No.13A110543)the Doctoral Fundamental Research Fund of Hennan Normal University(11102)
文摘t Let F = Cay(G, S), R(G) be the right regular representation of G. The graph Г is called normal with respect to G, if R(G) is normal in the full automorphism group Aut(F) of F. Г is called a bi-normal with respect to G if R(G) is not normal in Aut(Г), but R(G) contains a subgroup of index 2 which is normal in Aut(F). In this paper, we prove that connected tetravalent edge-transitive Cayley graphs on PGL(2,p) are either normal or bi-normal when p ≠ 11 is a prime.
文摘Let R be a commutative ring and U(R)the multiplicative group of unit elements of R.In 2012,Khashyarmanesh et al.defined the generalized unit and unitary Cayley graph,T(R,G,S),corresponding to a multiplicative subgroup G of U(R)and a nonempty subset S of G with S^(-1)={s^(-1)|s∈S}■S,asthegraphwithvertexsetR and two distinct vertices x and y being adjacent if and only if there exists s∈S such that x+sy∈G.In this paper,we characterize all Artinian rings R for which T(R,U(R),S)is projective.This leads us to determine all Artinian rings whose unit graphs,unitary Cayley graphs and co-maximal graphs are projective.In addition,we prove that for an Artinian ring R for which T(R,U(R),S)has finite nonorientable genus,R must be a finite ring.Finally,it is proved that for a given positive integer k,the number of finite rings R for which T(R,U(R),S)has nonorientable genus k is finite.
基金This work is supported by the National Natural Science Foundation of China (Grant Nos. 11671344 and 11531011).
文摘Let Sn denote the symmetric group of degree n with n 〉 3, S = {cn = (1 2…n), cn^-1, (1 2)} and Fn=Cay(Sn, S) be the Cayley graph on Sn with respect to S. In this paper, we show that Fn (n 〉 13) is a normal Cayley graph, and that the full automorphism group of Fn is equal to Aut(Гn) = R(Sn) (Inn(C))≌- Sn×Z2, where R(Sn) is the right regular representation of Sn,φ = (1 2)(3 n)(4 n-1)(5 n-2)... (∈ Sn), and Inn(C) is the inner isomorphism of Sn induced by φ .
基金supported by the National Natural Science Foundation of China(11701503,11861076,12061089,11761079)Yunnan Applied Basic Research Projects(2018FB003,2019FB139)the third author was supported by the National Natural Science Foundation of China(11601263,11701321).
文摘A Cayley graph Г=Cay(G,S)is said to be normal if G is normal in Aut Г.In this paper,we investigate the normality problem of the connected 11-valent symmetric Cayley graphs Г of finite nonabelian simple groups G,where the vertex stabilizer A_(u) is soluble for A=Aut Г and v∈∨Г.We prove that either Г is normal or G=A_(5),A_(10),A_(54),A_(274),A_(549) or A_(1099).Further,11-valent symmetric nonnormal Cayley graphs of As,A54 and A274 are constructed.This provides some more examples of nonnormal 11-valent symmetric Cayley graphs of finite nonabelian simple groups after the first graph of this kind(of valency 11)was constructed by Fang,Ma and Wang in 2011.