We study the unitary Cayley graph of a matrix semiring. We find bounds for its diameter, clique number and independence number, and determine its girth. We also find the relationship between the ...diameter and the clique number of a unitary Cayley graph of a semiring S and a matrix semiring over S.
A subset C of the vertex set of a graph Γ is called a perfect code in Γ if every vertex of Γ is at distance no more than 1 to exactly one vertex of C. A subset C of a group G is called a perfect code ...of G if C is a perfect code in some Cayley graph of G. In this paper we give sufficient and necessary conditions for a subgroup H of a finite group G to be a perfect code of G. Based on this, we determine the finite groups that have no nontrivial subgroup as a perfect code, which answers a question by Ma, Walls, Wang and Zhou.
Let Γ be a graph with vertex set V, and let a and b be nonnegative integers. A subset C of V is called an (a,b)-regular set in Γ if every vertex in C has exactly a neighbors in C and every vertex in ...V∖C has exactly b neighbors in C. In particular, (0,1)-regular sets and (1,1)-regular sets in Γ are called perfect codes and total perfect codes in Γ, respectively. A subset C of a group G is said to be an (a,b)-regular set of G if there exists a Cayley graph of G which admits C as an (a,b)-regular set. In this paper we prove that, for any generalized dihedral group G or any group G of order 4p or pq for some primes p and q, if a nontrivial subgroup H of G is a (0,1)-regular set of G, then it must also be an (a,b)-regular set of G for any 0⩽a⩽|H|−1 and 0⩽b⩽|H| such that a is even when |H| is odd. A similar result involving (1,1)-regular sets of such groups is also obtained in the paper.
Let G be a simple graph. A vertex-subset (edge-subset) D⊆V(G) (D⊆E(G)) is called an m-restricted vertex-cut (edge-cut) of G if G−D is disconnected and δ(G−D)≥m. The m-restricted (edge) connectivity ...of G, denoted by κm(G) (λm(G)), is the size of a smallest m-restricted vertex-cut (edge-cut). Let B be the symmetric group on n={1,2,…,n} and X be a set of transposition of B. Let G(X) be the generating graph with V(G(X))=n and E(G(X))={(c,d)∣(c,d)∈X}. If G(X) is isomorphic to a tree, the Cayley graph Cay(B,X), denoted by Γn, is the so called Cayley graph generated by transposition tree. Specially, if G(X) is isomorphic to a path, then Γn is the well-known bubble sort graph Bn; if G(X) is isomorphic to a star, then Γn is star graph Sn. In this work, we investigate m-restricted (edge) connectivity of Cayley graph Γn, whose generating graph G(X) has maximum matching number h. When 1≤m≤h, we show that the m-restricted (edge) connectivity of Γn is κm(Γn)=2m(n−1−m) (resp., λm(Γn)=2m(n−1−m)).
Let G be a finite group and Γ be a (di)graph. Then Γ is called an n-Cayley (di)graph over G if
admits a semiregular subgroup isomorphic to G with n orbits on
. In this paper, we determine the ...normalized Laplacian polynomial of n-Cayley (di)graphs over a group G in terms of irreducible representations of G. We give exact formulas for the normalized Laplacian eigenvalues of 2-Cayley graphs over abelian groups. Among other results, as an application, we prove that the degree-Kirchhoff index of the n-sunlet graph is
.
•We give explicit expressions for the HS-splitting fields of abelian mixed Cayley graphs. In addition, we derive a formula to calculate their corresponding HS-algebraic degrees. Moreover, we ...characterize all HS-integral abelian mixed Cayley graphs.•The method we used involving much mathematics.
For an n-vertex mixed graph A, let HS(A) be the Hermitian-adjacency matrix of the second kind of A and ΦA(HS,λ)=det(λIn−HS(A)) the characteristic polynomial of HS(A). The splitting field of ΦA(HS,λ) is referred to as the HS-splitting field of A. Its extension degree over the rational number field Q is referred to as the HS-algebraic degree of A, and A is said to be HS-integral if all eigenvalues of HS(A) are integers. In this paper, we give explicit expressions for the HS-splitting fields of abelian mixed Cayley graphs. In addition, we derive a formula to calculate their corresponding HS-algebraic degrees. Moreover, we characterize all HS-integral abelian mixed Cayley graphs.
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.