Edge-transitive bi-Cayley graphs Conder, Marston; Zhou, Jin-Xin; Feng, Yan-Quan ...
Journal of combinatorial theory. Series B,
November 2020, 2020-11-00, Volume:
145
Journal Article
Peer reviewed
Open access
A graph Γ admitting a group H of automorphisms acting semi-regularly on the vertices with exactly two orbits is called a bi-Cayley graph over H. This generalisation of a Cayley graph gives a class of ...graphs that includes many important examples such as the Petersen graph, the Gray graph and the Hoffman-Singleton graph. A bi-Cayley graph Γ over a group H is called normal if H is normal in the full automorphism group of Γ, and almost-normal edge-transitive if the normaliser of H in the full automorphism group of Γ is transitive on the edges of Γ. In this paper, we give a characterisation of almost-normal edge-transitive bi-Cayley graphs, and in particular, we give a detailed description of 2-arc-transitive normal bi-Cayley graphs. Using this, we investigate three classes of bi-Cayley graphs, namely those over abelian groups, dihedral groups and metacyclic p-groups. We find that under certain conditions, ‘almost-normal edge-transitive’ is the same as ‘normal’ for graphs in these three classes. As a by-product, we obtain a complete classification of all connected trivalent edge-transitive graphs of girth at most 6. Also we answer some open questions from the literature about these and related classes of graphs, posed by Li (in Proc. Amer. Math. Soc. 133 (2005)), Marušič and Potočnik (in Eur. J. Comb. 22 (2001)) and Marušič and Šparl (in J. Algebr. Comb. 28 (2008)), and we correct a major error in a recent paper by Li, Song and Wang (in J. Comb. Theory Ser. A 120 (2013)).
Consider a simple, connected graph Γ with n vertices. Let C be a code of length n with its coordinates corresponding to the vertices of Γ. We define C as a storage code on Γ if, for any codeword c ∈ ...C , the information at each coordinate of c can be recovered by accessing its neighboring coordinates. The main problem here is to construct high-rate storage codes on triangle-free graphs. In this paper, we employ the polynomial method to address a question proposed by Barg and Zémor in 2022, demonstrating that the BCH family of storage codes on triangle-free Cayley graphs achieves a unit rate. Furthermore, we generalize the construction of the BCH family and obtain more storage codes of unit rate on triangle-free graphs. We also compare the BCH family with the other known constructions by examining the rate of convergence of 1/(1- R ( C n )) with respect to the length n , where R ( C n ) is the rate of code C n . At last, we reveal a connection between the storage codes on triangle-free graphs and the Ramsey number R (3, t ), which leads to an upper bound for the rate of convergence of 1/(1 - R ( C n )).
For a digraph Γ, if F is the smallest field that contains all roots of the characteristic polynomial of the adjacency matrix of Γ, then F is called the splitting field of Γ. The extension degree of F ...over the field of rational numbers Q is said to be the algebraic degree of Γ. A digraph is a semi-Cayley digraph over a group G if it admits G as a semiregular automorphism group with two orbits of equal size. A semi-Cayley digraph SC(G,T11,T22,T12,T21) is called quasi-abelian if each of T11,T22,T12 and T21 is a union of some conjugacy classes of G. This paper determines the splitting field and the algebraic degree of a quasi-abelian semi-Cayley digraph over any finite group in terms of irreducible characters of groups. This work generalizes the previous works on algebraic degrees of Cayley graphs over abelian groups and any group having a subgroup of index 2, and semi-Cayley digraphs over abelian groups.
The classical Pauli group can be obtained as the central product of the dihedral group of 8 elements with the cyclic group of order 4. Inspired by this characterization, we introduce the notion of ...central product of Cayley graphs, which allows to regard the Cayley graph of a central product of groups as a quotient of the Cartesian product of the Cayley graphs of the factor groups. We focus our attention on the Cayley graph Cay(Pn,SPn) of the generalized Pauli group Pn on n-qubits; in fact, Pn may be decomposed as the central product of finite 2-groups, and a suitable choice of the generating set SPn allows us to recognize the structure of central product of graphs in Cay(Pn,SPn).
Using this approach, we are able to recursively construct the adjacency matrix of Cay(Pn,SPn) for each n≥1, and to explicitly describe its spectrum and the associated eigenvectors. It turns out that Cay(Pn,SPn) is a (3n+2)-regular bipartite graph on 4n+1 vertices, and it has integral spectrum. This is a highly nontrivial property if one considers that, by choosing as a generating set for P1 the three classical Pauli matrices, one gets the so-called Möbius-Kantor graph, belonging to the class of generalized Petersen graphs, whose spectrum is not integral.
In this paper we compute bounds for signless Laplacian energy, distance signless Laplacian eigenvalues and signless Laplacian energy of unitary addition Cayley graph
$ G_{n} $
G
n
. We also obtain ...distance Laplacian eigenvalues and distance Laplacian energy of
$ G_{n} $
G
n
.
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.
In this paper, we characterize when t-type one-matching (respectively, homogeneous) bi-Cayley graphs over finite cyclic groups are integral. We also give a necessary and sufficient condition for some ...integral t-type one-matching (respectively, homogeneous) bi-Cayley graphs over finite cyclic groups of prime power order to be Ramanujan.
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).
PDF
