We define the signed Cayley graph on Cayley graph Xn denoted by Sn, and study several properties such as balancing, clusterability and sign-compatibility of the signed Cayley graph Sn. Apart from it ...we also study the characterization of the canonical consistency of Sn, for some n.
A graph is half-arc-transitive if its full automorphism group acts transitively on vertices and edges, but not on arcs. Let p be a prime. It is known that there exists no tetravalent ...half-arc-transitive graph of order p or p2. All the tetravalent half-arc-transitive graphs of order p3 or p4 have been classified in two previous papers 9,23. As a continuation, in this paper, a classification is given of all tetravalent half-arc-transitive graphs of order p5.
An (r,z,k)-mixed graph G has every vertex with undirected degree r, directed in- and out-degree z, and diameter k. In this paper, we study the case r=z=1, proposing some new constructions of ...(1,1,k)-mixed graphs with a large number of vertices N. Our study is based on computer techniques for small values of k and the use of graphs on alphabets for general k. In the former case, the constructions are either Cayley or lift graphs. In the latter case, some infinite families of (1,1,k)-mixed graphs are proposed with diameter of the order of 2log2N.
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 )).
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
.
Suppose that is a finite group and is a non-empty subset of such that and . Suppose that is the Cayley graph whose vertices are all elements of and two vertices and are adjacent if and only ...if . In this paper, we introduce the generalized Cayley graph denoted by that is a graph with vertex set consists of all column matrices which all components are in and two vertices and are adjacent if and only if , where is a column matrix that each entry is the inverse of similar entry of and is matrix with all entries in , is the transpose of and . In this paper, we clarify some basic properties of the new graph and assign the structure of when is complete graph , complete bipartite graph and complete 3-partite graph for every .
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
