Search

Given a graph X with a Hamilton cycle C, the compression factor κ (X , C) of C is the order of the largest cyclic subgroup of Aut (C) ∩ Aut (X) , and the Hamilton compression κ (X) of X is the maximum of κ (X , C) where C runs over all Hamilton cycles in X. Generalizing the well-known open problem regarding the existence of vertex-transitive graphs without Hamilton paths/cycles, it was asked by Gregor et al. (Ann Comb, arXiv:2205.08126v1, https://doi.org/10.1007/s00026-023-00674-y, 2023) whether for every positive integer k, there exists infinitely many vertex-transitive graphs (Cayley graphs) with Hamilton compression equal to k. Since an infinite family of Cayley graphs with Hamilton compression equal to 1 was given there, the question is completely resolved in this paper in the case of Cayley graphs with a construction of Cayley graphs of semidirect products Z p ⋊ Z k where p is a prime and k ≥ 2 a divisor of p - 1 . Further, infinite families of non-Cayley vertex-transitive graphs with Hamilton compression equal to 1 are given. All of these graphs being metacirculants, some additional results on Hamilton compression of metacirculants of specific orders are also given. [ABSTRACT FROM AUTHOR]

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 C a y (P n , S P n ) of the generalized Pauli group P n on n -qubits; in fact, P n may be decomposed as the central product of finite 2-groups, and a suitable choice of the generating set S P n allows us to recognize the structure of central product of graphs in C a y (P n , S P n ). Using this approach, we are able to recursively construct the adjacency matrix of C a y (P n , S P n ) for each n ≥ 1 , and to explicitly describe its spectrum and the associated eigenvectors. It turns out that C a y (P n , S P n ) is a (3 n + 2) -regular bipartite graph on 4 n + 1 vertices, and it has integral spectrum. This is a highly nontrivial property if one considers that, by choosing as a generating set for P 1 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. [ABSTRACT FROM AUTHOR]

Symmetry properties are of vital importance for graphs. The famous Cayley graph is a good mathematical model as its high symmetry. The normality of the graph can well reflect the symmetry of the graph. In this paper, we characterize the normality of the direct product of Cayley graphs and give a sufficient and necessary condition for the direct product of two graphs to be a Cayley graph. Moreover, a sufficient and necessary condition for judging the normality of the direct product of two graphs is given. [ABSTRACT FROM AUTHOR]

Let Γ = (V (Γ),E(Γ)) be a graph. A subset C of V (Γ) is called a perfect code of Γ, when C is an independent set and every vertex of V (Γ)∖C is adjacent to exactly one vertex in C. Let Γ = Cay(G, S) be a Cayley graph of a finite group G. A subset C of G is called a perfect code of G, when there exists a Cayley graph Γ of G such that C is a perfect code of Γ. Recently, groups whose set of all subgroup perfect codes forms a chain are classified. Also, groups with no proper nontrivial subgroup perfect code are characterized. In this paper, we generalize it and classify groups whose set of all non-perfect code subgroups forms a chain. [ABSTRACT FROM AUTHOR]

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 V 0 and V 1. Let S ⊆ V 0 and T ⊆ V 1 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. [ABSTRACT FROM AUTHOR]

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 2 log 2 N. [ABSTRACT FROM AUTHOR]

Let s be a positive integer. A graph is s-transitive if its automorphism group is transitive on s-arcs but not on (s + 1)-arcs. In this paper, we study all tetravalent s-transitive graphs of order 6p2. [ABSTRACT FROM AUTHOR]

In this paper, we consider the Cayley regression problem of the cyclic groups and the dihedral groups. We give the sufficient and necessary conditions for the cyclic group ℤn to be a Cayley regression. Moreover, the dihedral group D2n is a 3-Cayley regression if n is a prime power. [ABSTRACT FROM AUTHOR]

Based on irreducible representations of generalized quaternion groups, closed‐form formulae of Kirchhoff indices and resistance distances between vertex pairs of Cayley graphs on these groups are given. Closed‐form formulae of Kirchhoff indices and resistance distances between vertex pairs of Cayley graphs on quaternion groups are given by using its irreducible representations. [ABSTRACT FROM AUTHOR]

We develop a theory of covering digraphs, similar to the theory of covering spaces. By applying this theory to Cayley digraphs, we build a "bridge" between GLMY-theory and group homology theory, which helps to reduce path homology calculations to group homology computations. We show some cases where this approach allows us to fully express path homology in terms of group homology. To illustrate this method, we provide a path homology computation for the Cayley digraph of the additive group of rational numbers with a generating set consisting of inverses to factorials. The main tool in our work is a filtered simplicial set associated with a digraph, which we call the filtered nerve of a digraph. [ABSTRACT FROM AUTHOR]

It is proved that Tutte's 3-flow conjecture is true for Cayley graphs on groups of order 8p where p is an odd prime. [ABSTRACT FROM AUTHOR]

It is proved that Tutte's 3-flow conjecture is true for Cayley graphs on groups of order 8p where p is an odd prime. [ABSTRACT FROM AUTHOR]

R. Lyons, R. Pemantle and Y. Peres (Ann. Probab. 24 (4), 1996, 1993–2006) conjectured that for a Cayley graph G with a growth rate gr(G) > 1, the speed of a biased random walk exists and is positive for the biased parameter λ ∈ (1, gr(G)). And Gabor Pete (Probability and geometry ´ on groups, Chaper 9, 2024) sheds light on the intricate relationship between the spectral radius of the graph and the speed of the biased random walk. Here, we focus on an example of a Cayley graph, a free product of complete graphs. In this paper, we establish the continuity of the spectral radius of biased random walks with respect to the bias parameter in this class of Cayley graphs. Our method relies on the Kesten-Cheeger-Dodziuk-Mohar theorem and the analysis of generating functions. [ABSTRACT FROM AUTHOR]

In this paper the zero forcing number as well as propagation time of Cay(G, Ω), where G is a finite group and Ω ⊂ G\{1} is an inverse closed generator set of G is studied. In particular, it is shown that the propagation time of Cay(G, Ω) is at most two for some special generators. [ABSTRACT FROM AUTHOR]

The neighbor connectivity refers to the minimum number of vertices whose removal, along with their neighbors, causes a previously connected graph to become disconnected. In this paper we focus on Cayley graphs constructed from the symmetric group Sn. We investigate the bounds of the neighbor connectivity for two cases: when the generating graph is a tree, and when it is a unicyclic graph with a unique cycle of length m, specifically considering cases where m = 3, m = n - 1, or m = n. [ABSTRACT FROM AUTHOR]

Cayley graph is a graph that encodes the abstract structure of a group. It gives a way of encoding information about a group in a graph. On the other hand, hypergroup is a generalization of group in which the composition of any two elements is a non-empty set. The purpose of this paper is to find a suitable generalization of Cayley graphs to cover hypergroups. More precisely, we introduce generalized Cayley graphs over hypergroups, study their properties and find a simple tool to construct large connected GCH-graphs from smaller GCH-graphs by using graph product. [ABSTRACT FROM AUTHOR]

We show that the category of X-generated E-unitary inverse monoids with greatest group image G is equivalent to the category of G-invariant, finitary closure operators on the set of connected subgraphs of the Cayley graph of G. Analogously, we study F-inverse monoids in the extended signature (· , 1 , - 1 , m) , and show that the category of X-generated F-inverse monoids with greatest group image G is equivalent to the category of G-invariant, finitary closure operators on the set of all subgraphs of the Cayley graph of G. As an application, we show that presentations of F-inverse monoids in the extended signature can be studied by tools analogous to Stephen's procedure in inverse monoids, in particular, we introduce the notions of F-Schützenberger graphs and P-expansions. [ABSTRACT FROM AUTHOR]

We say that a Hamilton cycle C = (x 1 , ... , x n) in a graph G is k-symmetric, if the mapping x i ↦ x i + n / k for all i = 1 , ... , n , where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices x 1 , ... , x n equidistantly on a circle and draw the edges of G as straight lines, then the drawing of G has k-fold rotational symmetry, i.e., all information about the graph is compressed into a 360 ∘ / k wedge of the drawing. The maximum k for which there exists a k-symmetric Hamilton cycle in G is referred to as the Hamilton compression of G. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases, we determine their Hamilton compression exactly, and in other cases, we provide close lower and upper bounds. The constructed cycles have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced. [ABSTRACT FROM AUTHOR]

Cayley and nilpotent graphs arise from the interaction between graph theory and algebra and are used to visualize the structures of some algebraic objects as groups and commutative rings. On the other hand, Green and Schroll introduced Brauer graph algebras and Brauer configuration algebras to investigate the algebras of tame and wild representation types. An appropriated system of multisets (called a Brauer configuration) induces these algebras via a suitable bounded quiver (or bounded directed graph), and the combinatorial properties of such multisets describe corresponding indecomposable projective modules, the dimensions of the algebras and their centers. Undirected graphs are examples of Brauer configuration messages, and the description of the related data for their induced Brauer configuration algebras is said to be the Brauer analysis of the graph. This paper gives closed formulas for the dimensions of Brauer configuration algebras (and their centers) induced by Cayley and nilpotent graphs defined by some finite groups and finite commutative rings. These procedures allow us to give examples of Hamiltonian digraph constructions based on Cayley graphs. As an application, some quantum entangled states (e.g., Greenberger–Horne–Zeilinger and Dicke states) are described and analyzed as suitable Brauer messages. [ABSTRACT FROM AUTHOR]

In this paper, we provide a brief introduction to the main notions of geometric group theory and of asymptotic topology of finitely generated groups. We will start by presenting the basis of discrete groups and of the topology at infinity, then we will state some of the main theorems in these fields. Our aim is to give a sample of how the presence of a group action may affect the geometry of the underlying space and how in many cases topological methods may help the determine solutions of algebraic problems which may appear unrelated. [ABSTRACT FROM AUTHOR]

Suppose that G is a finite group and S is a non-empty subset of G such that e ∉ S and S -1 ⊆ S. Suppose that Cay(G, S) is the Cayley graph whose vertices are all elements of G and two vertices x and y are adjacent if and only if xy -1 ∈ S. In this paper, we introduce the generalized Cayley graph denoted by Caym(G,S) that is a graph with vertex set consists of all column matrices Xm which all components are in G and two vertices Xm and Ym are adjacent if and only if Xm[(Ym) -1 ] t ∈ M(S), where Ym -1 is a column matrix that each entry is the inverse of similar entry of Ym and M(S) is m × m matrix with all entries in S, [Y -1 ] t is the transpose of Y-1 and m ≥ 1. We aim to determine the structure of Caym(G,S) when G is the dihedral group of order 2n and L S |= 3 for every m ≥ 2, n ≥ 3. [ABSTRACT FROM AUTHOR]

The exact formula for the average hitting time (HT, as an abbreviation) of simple random walks on Cay (Z N , { ± 1 , ± 2 }) was given by Y. Doi et al.. Y. Doi et al. give a simple formula for the HT's of simple random walks on Cay (Z N , { ± 1 , ± 2 }) by using an elementary method. In this paper, using an elementary method also used by Y. Doi et al., we give a simple formula for HT's of simple random walks on Cay (Z N , { + 1 , + 2 }). [ABSTRACT FROM AUTHOR]

Let ᴦ be a k-regular graph with the second maximum eigen-value λ. Then ᴦ is a Ramanujan graph if λ ≤ 2√k-1. Let G be a finite group and ᴦ = Cay(G; S) be a Cayley graph related to G. The aim of this paper is to investigate the Ramanujan Cayley graphs of sporadic groups. [ABSTRACT FROM AUTHOR]

Perfect state transfer has attracted much interest recently due to its significant applications in quantum information processing and cryptography. In this paper, we investigate perfect state transfer on Cayley graphs over dicyclic groups. Utilizing the representations and characters of dicyclic groups $ T_{4n} $ T 4 n , some necessary and sufficient conditions for Cayley graphs over dicyclic groups admitting perfect state transfer are provided. By those results, some concrete constructions are presented. [ABSTRACT FROM AUTHOR]

Let L be a lattice. For a natural number n, we associate a simple graph, denoted by ΓnL, with Ln\ {0} as the vertex set and two distinct vertices X and Y being adjacent if and only if there exists an n×n lower triangular matrix A over L such that AXT = YT or AYT = XT, where for a matrix B, BT is the matrix transpose of B. In this paper, we study some basic properties of ΓnL. Also, we investigate the genus number of the generalized Cayley graph ΓnL. [ABSTRACT FROM AUTHOR]

Let S be a subset of a finite group Γ. The Cayley signed graph, denoted by Σ = CayΣ(S, σ) has vertex set Γ and two distinct vertices x, y ∈ Γ are joined by an edge from x to y if and only if there exists s ∈ S such that x = sy, where Σ is a signed graph whose underlying graph is Γ and σ : E(Γ) → {+, -} is a function defined as ... In this manuscript, we have characterized the Cayley set and generating sets for which Cayley signed graphs are canonically consistent. [ABSTRACT FROM AUTHOR]

Let R be a finite commutative ring with non-zero identity and Z (R) ∗ be the set of all non-zero zero-divisors of R. In this paper, for a non-empty subset S of Z (R) ∗ , we introduce a new graph, denoted by Γ (R , S) , with vertex set Z (R) ∗ and two distinct vertices x and y are adjacent if and only if there is s ∈ S such that s x = 0 = s y. Then, we investigate some properties of the graph Γ (R , S). [ABSTRACT FROM AUTHOR]

In this paper, we explore connected Cayley graphs on non-abelian groups of order 5p², where p is a prime greater than 5, and Sylow p-subgroup is cyclic with respect to tetravalent sets that encompass elements with different orders. We prove that these graphs are normal; however, they are not normal edge-transitive, arc-transitive, nor half-transitive. Additionally, we establish that the group is a 5-CI-group. [ABSTRACT FROM AUTHOR]

This paper studies a sliding block puzzle defined on the two by three grid, which we call the 5-puzzle. Our main aim in this paper is to show a fine geometric property of the graph representing the transitions of the positions of the 5-puzzle. We show that by identifying every position with its 180° rotation and applying path contractions, the soccer ball graph is obtained. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Let be a finite group and S be a non-empty subset of A Cayley graph of the group denoted by Cay(S) is defined as a simple graph that its vertices are the elements of and two vertices u and v are adjacent if uv1 2. The minimum edge dominating energy of Cayley graph Cay(; S) is equal to the sum of the absolute values of eigenvalues of the minimum edge dominating matrix of graph Cay(; S). In this paper, we estimate the minimum edge dominating energy of the Cayley graphs for the finite group Sn. [ABSTRACT FROM AUTHOR]

Consider an assignment of bits to the vertices of a connected graph Γ (V , E) with the property that the value of each vertex is a function of the values of its neighbors. A collection of such assignments is called a storage code of length |V| on Γ . In this paper we construct an infinite family of linear storage codes on triangle-free graphs with rates arbitrarily close to one. [ABSTRACT FROM AUTHOR]

In this paper, we take a modest first step towards a systematic study of chromatic numbers of Cayley graphs on abelian groups. We lose little when we consider these graphs only when they are connected and of finite degree. As in the work of Heuberger and others, in such cases the graph can be represented by an m × r integer matrix, where we call m the dimension and r the rank. Adding or subtracting rows produces a graph homomorphism to a graph with a matrix of smaller dimension, thereby giving an upper bound on the chromatic number of the original graph. In this article we develop the foundations of this method. As a demonstration of its utility, we provide an alternate proof of Payan's theorem, which states that a cubelike graph (i.e., a Cayley graph on the product Z 2 × ⋯ × Z 2 of the integers modulo 2 with itself finitely many times) cannot have chromatic number 3. In a series of follow-up articles using the method of Heuberger matrices, we completely determine the chromatic number in cases with small dimension and rank, as well as prove a generalization of Zhu's theorem on the chromatic number of 6-valent integer distance graphs. [ABSTRACT FROM AUTHOR]

Let S be a pseudo-unitary homogeneous (graded) inverse semigroup with zero 0, that is, an inverse semigroup with zero, and with a family { S δ } δ ∈ Δ of nonzero subsets of S, called components of S, indexed by a partial groupoid Δ , that is, by a set with a partial binary operation, such that S = ⋃ δ ∈ Δ S δ , and: i) S ξ ∩ S η ⊆ { 0 } for all distinct ξ , η ∈ Δ ; ii) S ξ S η ⊆ S ξ η whenever ξ η is defined; iii) S ξ S η ⊈ { 0 } if and only if the product ξ η is defined; iv) for every idempotent element ϵ ∈ Δ , the subsemigroup S ϵ is with identity 1 ϵ ; v) for every x ∈ S there exist idempotent elements ξ , η ∈ Δ such that 1 ξ x = x = x 1 η ; vi) 1 ξ 1 η = 1 ξ η whenever ξ η ∈ Δ is an idempotent element, where ξ , η are idempotent elements of Δ . Let A be a subset of the union of the subsemigroup components of S, which does not contain 0. By Cay (S ∗ , A) we denote a graph obtained from the Cayley graph Cay (S , A) by removing 0 and its incident edges. We characterize vertex-transitivity of Cay (S ∗ , A) and relate it to the vertex-transitivity of its subgraph whose vertex set is S μ \ { 0 } , where μ is the maximum element of the set of all idempotent elements of Δ , with respect to the natural order. [ABSTRACT FROM AUTHOR]

In this paper, we study near approximations in Cayley graphs, which are an extended study of rough approximations in Cayley graphs by using more than one equivalence relations. Furthermore, we introduce the notion of a near edge Cayley graphs, expanded to the near vertex pseudo-Cayley graphs and near pseudo-Cayley graphs. Some theorems dealing with the properties discussed are derived. We illustrate some examples especially in cyclic groups for simplification in graphs visualization. [ABSTRACT FROM AUTHOR]

A graphical regular representation of a group G is a Cayley graph of G whose full automorphism group is equal to the right regular permutation representation of G. In this paper, we prove that for Ree groups Ree (q) with q > 3, with probability tending to 1 as q → ∞ , a random involution y together with a fixed element x with order q – 1 gives rise to a cubic graphical regular representation of Ree (q) . A similar result involving a fixed element with order q + 3 q + 1 is also proved with the help of certain properties of Ree (q) given in [Leemans, D. Liebeck, M. W. (2017). Chiral polyhedra and finite simple groups. Bull. London Math. Soc. 49: 581–592]. [ABSTRACT FROM AUTHOR]

Following the discovery of an artificial protein cage with a paradoxical geometry, we extend the concept of homogeneous symmetric congruent equivalent near-miss polyhedral cages, for which all the faces are equivalent, and define bi-homogeneous symmetric polyhedral cages made of two different types of faces, where all the faces of a given type are equivalent. We parametrise the possible connectivity configurations for such cages, analytically derive p-cages that are regular, and numerically compute near-symmetric p-cages made of polygons with 6 to 18 edges and with deformation not exceeding 10%. [ABSTRACT FROM AUTHOR]

In this paper, firstly, we will give a formula for the spectrum of a line graph of a circulant graph. Secondly, a formula for the spectrum of a line graph of a Cayley graph over an abelian group will be given. [ABSTRACT FROM AUTHOR]

A Cayley graph Cay (G , S) on a finite group G is said to be normal if the right regular representation R (G) of G is normal in the full automorphism group of Cay (G , S). In this paper, we classify all connected pentavalent non-normal Cayley graphs of order 2 p 2 with solvable automorphism groups and p > 3 a prime. [ABSTRACT FROM AUTHOR]

A perfect code in a graph Γ is a subset C of V (Γ) such that no two vertices in C are adjacent and every vertex in V (Γ) \ C is adjacent to exactly one vertex in C. Let G be a finite group and C a subset of G. Then C is said to be a perfect code of G if there exists a Cayley graph of G admiting C as a perfect code. It is proved that a subgroup H of G is a perfect code of G if and only if a Sylow 2-subgroup of H is a perfect code of G. This result provides a way to simplify the study of subgroup perfect codes of general groups to the study of subgroup perfect codes of 2-groups. As an application, a criterion for determining subgroup perfect codes of projective special linear groups PSL (2 , q) is given. [ABSTRACT FROM AUTHOR]

In this paper, we study the semilinear elliptic equation − Δ u + a (x) | u | p − 2 u − b (x) | u | q − 2 u = 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. [ABSTRACT FROM AUTHOR]

The diagnosability of a multiprocessor system is of great significance in measuring the reliability and faulty tolerance of interconnection networks. In this paper, we firstly study the diagnosability of a class of Cayley graphs |$Cay(H_n,S_n)$| under the PMC model. We prove that |$Cay(H_n,S_n)-F$| keeps the strong local diagnosability property even if it has the set |$F$| of |$(m-2)$| faulty edges and |$m-2$| is maximum number of faulty edges, where |$m$| is the regular degree of |$Cay(H_n,S_n)$|⁠. Secondly, we study the diagnosability of |$Cay(H_n,S_n)$| with conditional faulty edges under the PMC model. We prove that |$Cay(H_n,S_n)-F$| keeps strong local diagnosability property even if it has the set |$F$| of |$(3m-10)$| faulty edges, provided that each vertex of |$Cay(H_n,S_n)-F$| is incident with at least two fault-free edges, where |$3m-10$| is maximum number of faulty edges. Finally, we prove that |$Cay(H_n,S_n)-F$| keeps strong local diagnosability property no matter how many edges are faulty, provided that each vertex of |$Cay(H_n,S_n)-F$| is incident with at least four fault-free edges. [ABSTRACT FROM AUTHOR]

The minimum edge dominating energy of a graph G is defined as the sum of the absolute values of eigenvalues of the minimum edge dominating matrix of G. In this paper, for some finite symmetric groups Γ and subset S of Γ, the minimum edge dominating energy of the Cayley graph of the group Γ, denoted by Cay(Γ, S), is investigated. [ABSTRACT FROM AUTHOR]

S−1 ⊆ S. Suppose that Cay(G, S) is the Cayley graph whose vertices are all elements of G and two vertices x and y are adjacent if and only if xy−1 ∈ S. In this paper, we introduce the generalized Cayley graph denoted by Caym(G, S) which is a graph with a vertex set consisting of all column matrices Xm in which all components are in G and two vertices Xm and Ym are adjacent if and only if Xm[(Ym)−1]t ∈ M(S), where Ym−1 is a column matrix that each entry is the inverse of the similar entry of Ym and M(S) is m x m matrix with all entries in S, [Y−1]t is the transpose of Y−1 and m ≥ 1 and m∈ N. We aim to provide some basic properties of the new graph and determine the structure of Caym(G, S) when Cay(G, S) is a complete graph Kn for every m ≥ 2, n ≥ 3 and n, m∈ N. [ABSTRACT FROM AUTHOR]

Let $\Gamma $ be a graph of valency at least four whose automorphism group contains a minimally vertex-transitive subgroup G. It is proved that $\Gamma $ admits a nowhere-zero $3$ -flow if one of the following two conditions holds: (i) $\Gamma $ is of order twice an odd number and G contains a central involution; (ii) G is a direct product of a $2$ -subgroup and a subgroup of odd order. [ABSTRACT FROM AUTHOR]

In this paper, we study the square of generalized Hamming graphs by the properties of abelian groups, and characterize some isomorphisms between the square of generalized Hamming graphs and the non-complete extended p-sum of complete graphs. As applications, we determine the eigenvalues of the square of some generalized Hamming graphs. [ABSTRACT FROM AUTHOR]

We show that, up to isomorphism, there is a unique non-CI connected cubic Cayley graph on the dihedral group of order 2n for each even number n ≥ 4. This answers in the negative the question of Li whether all connected cubic Cayley graphs are CI-graphs (Discrete Math., 256, 301–334 (2002)). As an application, a formula is derived for the number of isomorphism classes of connected cubic Cayley graphs on dihedral groups, which generalises the earlier formula of Huang et al. dealing with the particular case when n is a prime (Acta Math. Sin., Engl. Ser., 33, 996–1011 (2017)). As another application, a short proof is also given for a result on sparse circulant matrices obtained by Wiedemann and Zieve (arXiv preprint, (2007)). [ABSTRACT FROM AUTHOR]

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 C a y (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 B n ; if G (X) is isomorphic to a star, then Γ n is star graph S n. 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) = 2 m (n − 1 − m) (resp., λ m (Γ n) = 2 m (n − 1 − m)). [ABSTRACT FROM AUTHOR]

To provide more accurate indicator for the fault-tolerance of networks, structure connectivity and substructure connectivity have been introduced. H-structure connectivity κ (G ; H) is the minimum number of subgraphs isomorphic to H in G, such that the deletion of those subgraphs disconnects G. H-substructure connectivity κ s (G ; H) is the minimum number of subgraphs isomorphic to connected subgraphs of H in G, such that the deletion of those subgraphs disconnects G. In this paper, we establish star structure and star substructure connectivity of Cayley graphs generated by transposition trees, which include bubble-sort graph and star graph. [ABSTRACT FROM AUTHOR]

Following the experimental discovery of several nearly symmetric protein cages, we define the concept of homogeneous symmetric congruent equivalent near-miss polyhedral cages made out of P-gons. We use group theory to parameterize the possible configurations and we minimize the irregularity of the P-gons numerically to construct all such polyhedral cages for P = 6 to P = 20 with deformation of up to 10%. [ABSTRACT FROM AUTHOR]