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.
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.
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 G be a generalized dicyclic group with identity 1. An inverse closed subset S of G∖{1} is called minimal if 〈S〉=G and there exists some s∈S such that 〈S∖{s,s−1}〉≠G. In this paper, we characterize ...distance-regular Cayley graphs Cay(G,S) of G under the condition that S is minimal.
Yin et al. (2021) 19 classified connected arc-transitive Cayley graphs on nonabelian simple groups with prime valency p≥11 and solvable vertex stabilizers. In this paper, we extend this result to ...bi-Cayley graphs. Let Γ be a connected arc-transitive bi-Cayley graph on a nonabelian simple group T with prime valency p≥5 and solvable vertex stabilizer. It is proved that either Γ is nonbipartite, or Γ is a normal bi-Cayley graph, or Γ is S-semisymmetric with (S,T,p)=(PSL2(11),A5,11),(PSL2(29),A5,29),(M23,M22,23), or (An,An−1,p) where p|n|pkl and k|l|(p−1). Moreover, example exists for each triple (S,T,p) above.
In this study, we investigate Hamiltonian cycles in the right-Cayley graphs of gyrogroups. More specifically, we give a gyrogroup version of the factor group lemma and show that some right-Cayley ...graphs of certain gyrogroups are Hamiltonian.