On diameter two Cayley graphs Jin, Wei; Tan, Li
Applied mathematics and computation,
12/2022, Volume:
434
Journal Article
Peer reviewed
•This paper studies diameter two Cayley graphs, and these graphs are interesting and important in mathematics.•The main result shows that the order of diameter 2 Cayley graphs satisfying that Rw is ...transitive in X2(w) but not in X(w) is unbounded.•The main result shows that the valency of diameter 2 Cayley graphs satisfying that Rw is transitive in X2(w) but not in X(w) is unbounded.
Let X be a Cayley graph whose diameter is 2. Set R:=Aut(X) and w∈V(X). In this paper, it is shown that: for every positive integer m at least 6, there is a such Cayley graph X of m points such that Rw acts transitively in X2(w) but not in X(w); for every positive integer k at least 3, there is a such graph X of valency k such that Rw is transitive in X2(w) but not in X(w).
A bipartite graph Γ is a bi-Cayley graph over a group H if H⩽Aut(Γ) acts faithfully and regularly on each part of Γ. In this paper, a complete classification is given of bi-quasiprimitive ...2-arc-transitive bi-Cayley graphs Γ over a finite simple group G such that G is non-normal in Aut(Γ).
In this paper, we study the semilinear elliptic equation−Δu+a(x)|u|p−2u−b(x)|u|q−2u=0 on a Cayley graph of a discrete group of polynomial growth with the homogeneous dimension N≥1, where 2≤p<q<+∞. We ...first prove the existence of positive solutions to the above equation with constant coefficients a¯,b¯. Then we establish a decomposition of Palais-Smale sequences for the functional with variable coefficients a(x),b(x), which tend to the constants a¯,b¯ at infinity.
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 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.