We define an addition signed Cayley graph on a unitary addition Cayley graph Gn represented by Σ n∧ , and study several properties such as balancing, clusterability and sign compatibility of the ...addition signed Cayley graph Σ n∧ . We also study the characterization of canonical consistency of Σ n∧ , for some n.
A mixed dihedral group is a group \(H\) with two disjoint subgroups \(X\) and \(Y\), each elementary abelian of order \(2^n\), such that \(H\) is generated by \(X\cup Y\), and \(H/H'\cong X\times ...Y\). In this paper, for each \(n\geq 2\), we construct a mixed dihedral \(2\)-group \(H\) of nilpotency class \(3\) and order \(2^a\) where \(a=(n^3+n^2+4n)/2\), and a corresponding graph \(\Sigma\), which is the clique graph of a Cayley graph of \(H\). We prove that \(\Sigma\) is semisymmetric, that is, \({\mathop{\rm Aut}}(\Sigma)\) acts transitively on the edges but intransitively on the vertices of \(\Sigma\). These graphs are the first known semisymmetric graphs constructed from groups that are not \(2\)-generated (indeed \(H\) requires \(2n\) generators). Additionally, we prove that \(\Sigma\) is locally \(2\)-arc-transitive, and is a normal cover of the `basic' locally \(2\)-arc-transitive graph \({\rm\bf K}_{2^n,2^n}\). As such, the construction of this family of graphs contributes to the investigation of normal covers of prime-power order of basic locally \(2\)-arc-transitive graphs – the `local' analogue of a question posed by C. H. Li.
Let L(G) denote the space of integer-valued length functions on a countable group G endowed with the topology of pointwise convergence. Assuming that G does not satisfy any non-trivial mixed ...identity, we prove that a generic (in the Baire category sense) length function on G is a word length and the associated Cayley graph is isomorphic to a certain universal graph U independent of G. On the other hand, we show that every comeager subset of L(G) contains 2ℵ0 “asymptotically incomparable” length functions. A combination of these results yields 2ℵ0 pairwise non-equivalent regular representations G→Aut(U). We also prove that generic length functions are virtually indistinguishable from the model-theoretic point of view. Topological transitivity of the action of G on L(G) by conjugation plays a crucial role in the proof of the latter result.
On the subgraphs of Cayley sum graphs Zhang, Jun-Yang; Yang, Yue-Yue
Discrete mathematics,
August 2023, 2023-08-00, Volume:
346, Issue:
8
Journal Article
Peer reviewed
The Cayley sum graph CS(G,A) of an abelian group G with a square-free subset A of G as the connection set is the graph with vertex set G and two vertices x and y being adjacent if and only if x+y∈A. ...In this paper we obtain two results on the subgraphs of CS(G,A). The first is that every connected component of CS(G,A) is either a bipartite Cayley graph of a generalized dihedral group or a connected Cayley sum graph of a subgroup of G. The second is that CS(G,A) has a spanning subgraph isomorphic to a cubic bipartite Cayley graph of a generalized dihedral group if A is of cardinality at least 4. As a by-product of the second result, we prove that CS(G,A) admits a nowhere-zero 3-flow whenever it is of valency at least 4.
A graph is said to be a bi-Cayley graph over a group H if it admits H as a group of automorphisms acting semiregularly on its vertex-set with two orbits of equal size. A bi-Cayley graph over a ...dicyclic group is called a bi-dicirculant. We give a classification of tetravalent connected vertex-transitive bi-dicirculants in this paper. As a byproduct, we prove that all connected tetravalent vertex-transitive bi-dicirculants are Cayley graphs.
Given a graph G, let S and T be two disjoint vertex subsets of equal size k in G. A many-to-many k-disjoint path cover of G joining S and T is a set of k vertex-disjoint paths between S and T that ...altogether cover every vertex of the graph. It is said to be paired if each vertex of S must be joined to a designated vertex of T, or unpaired otherwise. Let Γn be a Cayley graph generated by a transposition tree with bipartition V0 and V1. Let S⊆V0 and T⊆V1 be two vertex subsets of equal size two. It is shown in this paper that Γn has an unpaired many-to-many two-disjoint path cover joining S and T with at most n−4 faulty edges, where n≥4. The result is optimal with respect to the degree of Γn. As applications, the edge fault-tolerant two-disjoint path covers for the star network, bubble-sort network and modified bubble-sort network are derived.
•This paper derived the closed-form formulae for the hitting time, resistance distance and Kirchhoff index of the Cayley graphs over dicyclic and semi-dihedral groups. The main tool we used involves ...representation theory, linear algebra, and graph theory. Many technical calculations are also involved.
In this paper, using eigenvalues and eigenvectors, we derive the closed-form formulae for the hitting time, resistance distance and Kirchhoff index of the Cayley graphs over dicyclic and semi-dihedral groups.
Let Fq be a finite field of order q and let R be a finite commutative local ring which is not a field. Recently, three (resp. four) distinct eigenvalues of the unitary Cayley graph CMn(Fq) (resp. ...CMn(R)) have been determined in Rattanakangwanwong and Meemark (2020) 20. In this paper, completely explicit closed formulas for all the eigenvalues of CMn(Fq) and CMn(R) are obtained by using a new approach. As applications, the energy, the Kirchhoff index and the number of spanning trees of CMn(Fq) and CMn(R) are derived, respectively.
In this paper, graphs are undirected and loop-free and groups are finite. By Cn, Kn and Km,n we mean the cycle graph with n vertices, the complete graph with n vertices and the complete bipartite ...graph with parts size m and n, respectively. Also by Zn and Sn, we mean the cyclic group of order n and the symmetric group on n symbols, respectively. Let Γ be a simple connected graph with vertex set {v1,…,vn}. The distance between vertices vi and vj, denoted by d(vi,vj), is the length of a shortest path between them. The distance matrix of Γ, denoted by DΓ, is an n×n matrix whose (i,j)-entry is d(vi,vj). The distance characteristic polynomial of Γ, denoted by χD(Γ) is det(λI-D) and its zeros are the distance eigenvalues (in short D-eigenvalues) of Γ. If λ is a D-eigenvalue of Γ with multiplicity m, then we denote it by λm. Let λ1≥λ2≥…≥λn are the D-eigenvalues of Γ. Then λ1 is called distance spectral radius of Γ and we denote it by ρ(Γ). Also the multiset {λ1,…,λn} is denoted by SpecD(Γ). The studying of eigenvalues of distance matrices of graphs goes back to 1971, a paper by Graham and Pollack and thereafter attracted much more attention 2. There are several applications of distance matrix such as the design of communication networks, network follow algorithms, graph embedding theory and in chemistry, for more details see 2. Let G be a group and S=S-1 be a subset of G not containing the identity element of G. The Cayley graph of G with respect of S, denoted by Cay(G,S), is a graph with vertex set G and edge set {{g,sg}|g∈G,s∈S}. Cay(G,S) is a simple |S|-regular graph. Let x,y∈G. Then for all g∈G, x and y are adjacent if and only if xg and yg are adjacent. This implies that d(g,h)=d(1,hg-1) and d(g)=d(1) for all g,h∈G, where d(x)=y∈Gd(x,y). In the literature, the adjacency eigenvalues of Cayley graphs have been more widely used than the distance eigenvalues. A graph Γ is called distance (adjacency) integral if all the eigenvalues of its distance (adjacency) matrix are integers. A graph is called circulant if it is a Cayley graph over a cyclic group. Circulant graphs of valency 2 are cycles. In 2001, the distance eigenvalues of cycles computed 6. In 2010, the distance spectra of adjacency integral circulant graphs characterized and proved that these graphs are distance integral 9. In 2011, Rentlen discussed the distance eigenvalues of Cayley graphs of Coxeter groups using the irreducible representations of underlying group 10. He proved that the eigenvalues of the distance matrix of a Cayley graph of a real reflection group with respect to the set of all reflections are integral and provided a combinatorial formula for some such spectra. Then, Foster-Greenwood and Kriloff proved that the eigenvalues of the distance, adjacency, and codimension matrices of Cayley graphs of complex reflection groups with connection sets consisting of all reflections are integral and provided a combinatorial formula for the codimension spectra for a family of monomial complex reflection groups 5. In this paper, we determine the characteristic polynomial of the distance matrix of arbitrary Cayley graphs in terms of the irreducible representations of underlying groups. Let Γ=Cay(G,S) be a Cayley graph over a finite group G. It is well-known that one can determine the (adjacency) eigenvalues Γ by the irreducible representations of G, see for example 3, Corollary 7. In this paper, by a similar argument, we determine the distance eigenvalues of Γ in terms of the irreducible representations of G. Then, as an application of our result, we exactly determine the distance eigenvalues of some well-know Cayley graphs: cycles, n-prims, hexagonal torus network and cubic Cayley graphs over abelian groups. Results and discussion We construct an infinite family of distance integral Cayley graphs. Also we prove that a finite abelian group G admits a connected cubic distance integral Cayley graph if and only if G is isomorphic to one of the groups Z4, Z6, Z4×Z2, Z6×Z2, or Z2×Z2×Z2. Furthermore, up to isomorphism, there are exactly 5 connected cubic distance integral Cayley graphs over Abelian groups which are K4, K3,3, P3, P4 and P6, where Pn is the n-prism. Conclusion The following conclusions were drawn from this research. The characteristic polynomial of the distance matrix of Cayley graphs over a group G is determined by the irreducible representations of G. Exact formulas for n-prisms, hexagonal torus network and cubic Cayley graphs over Abelian groups are given. Infinite family of distance integral Cayley graphs are constructed. Cubic distance integral Cayley graphs over finite abelian groups are classified. By a similar argument, one can find all quartic distance integral Cayley graphs over finite Abelian groups. One can easily compute the distance eigenvalues of a Cayley graph using irreducible representations of the underlying group.In this paper, graphs are undirected and loop-free and groups are finite. By Cn, Kn and Km,n we mean the cycle graph with n vertices, the complete graph with n vertices and the complete bipartite graph with parts size m and n, respectively. Also by Zn and Sn, we mean the cyclic group of order n and the symmetric group on n symbols, respectively. Let Γ be a simple connected graph with vertex set {v1,…,vn}. The distance between vertices vi and vj, denoted by d(vi,vj), is the length of a shortest path between them. The distance matrix of Γ, denoted by DΓ, is an n×n matrix whose (i,j)-entry is d(vi,vj). The distance characteristic polynomial of Γ, denoted by χD(Γ) is det(λI-D) and its zeros are the distance eigenvalues (in short D-eigenvalues) of Γ. If λ is a D-eigenvalue of Γ with multiplicity m, then we denote it by λm. Let λ1≥λ2≥…≥λn are the D-eigenvalues of Γ. Then λ1 is called distance spectral radius of Γ and we denote it by ρ(Γ). Also the multiset {λ1,…,λn} is denoted by SpecD(Γ). The studying of eigenvalues of distance matrices of graphs goes back to 1971, a paper by Graham and Pollack and thereafter attracted much more attention 2. There are several applications of distance matrix such as the design of communication networks, network follow algorithms, graph embedding theory and in chemistry, for more details see 2. Let G be a group and S=S-1 be a subset of G not containing the identity element of G. The Cayley graph of G with respect of S, denoted by Cay(G,S), is a graph with vertex set G and edge set {{g,sg}|g∈G,s∈S}. Cay(G,S) is a simple |S|-regular graph. Let x,y∈G. Then for all g∈G, x and y are adjacent if and only if xg and yg are adjacent. This implies that d(g,h)=d(1,hg-1) and d(g)=d(1) for all g,h∈G, where d(x)=y∈Gd(x,y). In the literature, the adjacency eigenvalues of Cayley graphs have been more widely used than the distance eigenvalues. A graph Γ is called distance (adjacency) integral if all the eigenvalues of its distance (adjacency) matrix are integers. A graph is called circulant if it is a Cayley graph over a cyclic group. Circulant graphs of valency 2 are cycles. In 2001, the distance eigenvalues of cycles computed 6. In 2010, the distance spectra of adjacency integral circulant graphs characterized and proved that these graphs are distance integral 9. In 2011, Rentlen discussed the distance eigenvalues of Cayley graphs of Coxeter groups using the irreducible representations of underlying group 10. He proved that the eigenvalues of the distance matrix of a Cayley graph of a real reflection group with respect to the set of all reflections are integral and provided a combinatorial formula for some such spectra. Then, Foster-Greenwood and Kriloff proved that the eigenvalues of the distance, adjacency, and codimension matrices of Cayley graphs of complex reflection groups with connection sets consisting of all reflections are integral and provided a combinatorial formula for the codimension spectra for a family of monomial complex reflection groups 5. In this paper, we determine the characteristic polynomial of the distance matrix of arbitrary Cayley graphs in terms of the irreducible representations of underlying groups. Let Γ=Cay(G,S) be a Cayley graph over a finite group G. It is well-known that one can determine the (adjacency) eigenvalues Γ by the irreducible representations of G, see for example 3, Corollary 7. In this paper, by a similar argument, we determine the distance eigenvalues of Γ in terms of the irreducible representations of G. Then, as an application of our result, we exactly determine the distance eigenvalues of some well-know Cayley graphs: cycles, n-prims, hexagonal torus network and cubic Cayley graphs over abelian groups. Results and discussion We construct an infinite family of distance integral Cayley graphs. Also we prove that a finite abelian group G admits a connected cubic distance integral Cayley graph if and only if G is isomorphic to one of the groups Z4, Z6, Z4×Z2, Z6×Z2, or Z2×Z2×Z2. Furthermore, up to isomorphism, there are exactly 5 connected cubic distance integral Cayley graphs over Abelian groups which are K4, K3,3, P3, P4 and P6, where Pn is the n-prism. Conclusion The following conclusions were drawn from this research. In this paper, graphs are undirected and loop-free and groups are finite. By Cn, Kn and Km,n we mean the cycle graph with n vertices, the complete graph with n vertices and the complete bipartite graph with parts size m and n, respectively. Also by Zn and Sn, we mean the cyclic group of order n and the symmetric group on n symbols, respectively. Let Γ be a simple connected graph with vertex set {v1,…,vn}. The distance between vertices vi and vj, denoted by d(vi,vj), is the length of a shortest path between them. The distance matrix of Γ, denoted by DΓ, is an n×n matrix whose (i,j)-entry is d(vi,vj). The distance characteristic polynomial of Γ, denoted by χD(Γ) is det(λI-D) and its zeros are the distance eigenvalues (in short D-eigenvalues) of Γ. If λ is a D-eigenvalue of Γ with multiplicity m, then we deno
PDF
