Search

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]

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]

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]

In this paper, we extend our research on Cayley graphs of gyrogroups by exploring connections between the algebraic characteristics of gyrogroups and the combinatorial characteristics of their Cayley graphs. We look into some automorphisms of right Cayley graphs, give sufficient and necessary criteria for a right Cayley graph to be vertex-transitive by left gyrotranslations, and prove a similar result for quotient gyrogroups. Some sufficient and necessary criteria for a left gyroaddition to preserve edge color and for a gyration to be an automorphism on the graph are also given. Lastly, we show that certain Cayley graphs of a gyrogroup encode the gyroaddition table and provide an algorithm to compute the gyroaddition with the aid of the gyration table. [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 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 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]

In this paper, we introduce subgroup complementary addition Cayley graph SC + (G , H) and compute its graph invariants. Also, we prove that SC + (G , H) ≅ SC (G , H) if and only if v 2 ∉ H ̄ for all v ∈ H ̄ where H ̄ = G − H. [ABSTRACT FROM AUTHOR]

As a variant of Q n , Huang and Wu in [IEEE Transactions on Computers 46 (1997) 484–490] introduced the balanced hypercube B H n as an interconnection network topology for computing systems. In this paper, we show that B H n is a lexicographic product of two graphs, and using this, we show that every minimum cyclic vertex-cut of B H n isolates a 4-cycle, and prove that the edge neighbor connectivity of B H n is 2 n. [ABSTRACT FROM AUTHOR]

A perfect t -code in a graph Γ is a subset of V (Γ) such that every vertex of Γ is at a distance not more than t , to exactly one vertex of . In this paper, we present a new family of perfect t -codes in Cayley graphs of groups. We proposed the role of the subgroups of a group to create perfect t -codes by restricting the elements of the left transversal of the subgroups in the given group. Also, we introduce a new decoding algorithm for the all of perfect t -codes in Cayley graphs. These codes are able to correct every t -error pattern. [ABSTRACT FROM AUTHOR]

The Cayley graph generated by a transposition tree Γ n is a class of Cayley graphs that contains the star graph and the bubble sort graph. A graph G is called strongly Menger (SM for short) (edge) connected if each pair of vertices x , y are connected by min { d G (x) , d G (y) } (edge)-disjoint paths, where d G (x) , d G (y) are the degree of x and y respectively. In this paper, the maximally edge-fault-tolerant and the maximally vertex-fault-tolerant of Γ n with respect to the SM-property are found and thus generalize or improve the results in [19, 20, 22, 26] on this topic. [ABSTRACT FROM AUTHOR]

The transformation semigroup with restricted range T (X , Y) is the set of all functions from a set X into a non-empty subset Y of X. In this paper, we characterize Cayley graphs of T (X , Y) with the connection set A. Moreover, the undirected property of Cayley graphs Cay (T (X , Y) , A) is studied. [ABSTRACT FROM AUTHOR]

A graph Γ is said to be symmetric if its automorphism group Aut ⁡ (Γ) acts transitively on the arc set of Γ. We show that if Γ is a finite connected heptavalent symmetric graph with solvable stabilizer admitting a vertex-transitive non-abelian simple group G of automorphisms, then either G is normal in Aut ⁡ (Γ) , or Aut ⁡ (Γ) contains a non-abelian simple normal subgroup T such that G ≤ T and (G , T) is explicitly given as one of 11 possible exceptional pairs of non-abelian simple groups. If G is arc-transitive, then G is always normal in Aut ⁡ (Γ) , and if G is regular on the vertices of Γ , then the number of possible exceptional pairs (G , T) is reduced to 5. [ABSTRACT FROM AUTHOR]

In this paper, we determine the automorphism groups of a class of Frobenius groups, and then solve that under what condition they are REA-groups. As an application, we construct a type of normal edge-transitive Cayley graph. [ABSTRACT FROM AUTHOR]

A C 4 C 8 net is a trivalent decoration made by alternating square C 4 and octagons C 8 . It can cover either a cylinder or a tori. Cayley graph Cay (G , S) on a group G with connection set S has the elements of G as its vertices and an edge joining g and s g for all g ∈ S and s ∈ S. Motivated by Afshari's work, we show that the C 4 C 8 (S) [ n , n ] tori are Cayley graphs by constructing a regular subgroup of the automorphism group of C 4 C 8 (S) [ n , n ]. [ABSTRACT FROM AUTHOR]

We prove that the spectrum of a Cayley graph over a finite group with a normal generating set S containing with every its element s all generators of the cyclic group 〈s〉 is integral. In particular, a Cayley graph of a 2-group generated by a normal set of involutions is integral. We prove that a Cayley graph over the symmetric group of degree n no less than 2 generated by all transpositions is integral. We find the spectrum of a Cayley graph over the alternating group of degree n no less than 4 with a generating set of 3-cycles of the form (k i j) with fixed k, as {−n+1, 1−n+1, 22 −n+1, ..., (n−1)2 −n+1}. [ABSTRACT FROM AUTHOR]

The relative Cayley graph of a group G with respect to its proper subgroup H is a graph whose vertices are elements of G and two vertices h ∈ H and g ∈ G are adjacent if g = h c for some c ∈ C , where C is an inverse-closed subset of G. We study the relative Cayley graphs and, among other results, we discuss on their connectivity and forbidden structures, and compute some of their important numerical invariants. [ABSTRACT FROM AUTHOR]

A diagonal base of a Sylow 2-subgroup P n (2) of symmetric group S 2 n is a minimal generating set of this subgroup consisting of elements with only one nonzero coordinate in the polynomial representation. For different diagonal bases, Cayley graphs over P n (2) may have different girths (i.e. minimal lengths of cycles). In this paper, all possible values of girths of Cayley graphs over P n (2) with diagonal bases are calculated. A criterion for whenever such Cayley graph has girth equal to 4 is presented. [ABSTRACT FROM AUTHOR]

An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processors and communication links, respectively. Connectivity is an important metric for fault tolerance of interconnection networks. A graph G is said to be maximally local-connected if each pair of vertices u and v are connected by min { d G (u) , d G (v) } vertex-disjoint paths. In this paper, we show that Cayley graphs generated by m (≥ 7) transpositions are (m − 2) -fault-tolerant maximally local-connected and are also (m − 3) -fault-tolerant one-to-many maximally local-connected if their corresponding transposition generating graphs have a triangle, (m − 2) -fault-tolerant one-to-many maximally local-connected if their corresponding transposition generating graphs have no triangles. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, Cayley graphs generated by m (≥ 7) transpositions are (m − 1) -fault-tolerant maximally local-connected if their corresponding transposition generating graphs have no triangles. [ABSTRACT FROM AUTHOR]

In this paper, clique number and girth of the rough ideal-based rough edge Cayley graphs G (T (J)) and G (T (Ĵ)) , where J is the rough Ideal of the rough semiring (T , Δ , ∇) and Ĵ contains the nontrivial elements of J , are evaluated. We prove that the clique number of G (T (Ĵ)) is m + 1 and the clique number of G (T (J)) is m + 2. Girth of G (T (Ĵ)) and G (T (J)) is 3. These concepts are illustrated with examples. [ABSTRACT FROM AUTHOR]

Many models of genome rearrangement involve operations that are self-inverse, and hence generate a group acting on the space of genomes. This gives a correspondence between genome arrangements and the elements of a group, and consequently, between evolutionary paths and walks on the Cayley graph. Many common methods for phylogenetic reconstruction rely on calculating the minimal distance between two genomes; this omits much of the other information available from the Cayley graph. In this paper, we begin an exploration of some of this additional information, in particular describing the phylogeny as a Steiner tree within the Cayley graph, and exploring the "interval" between two genomes. While motivated by problems in systematic biology, many of these ideas are of independent group-theoretic interest. [ABSTRACT FROM AUTHOR]

In this paper we propose the concept of generalized semi-Cayley graphs, which is a combination of semi-Cayley graphs and generalized Cayley graphs. We study the isomorphisms and automorphisms of generalized semi-Cayley graphs and other related properties. [ABSTRACT FROM AUTHOR]

A C 4 C 8 net is a trivalent decoration made by alternating squares C 4 and octagons C 8 . It can cover either a cylinder or a torus. In this paper, we determine rhomboidal C 4 C 8 toris which are Cayley graphs. [ABSTRACT FROM AUTHOR]

In this paper we propose the concept of generalized semi-Cayley graphs, which is a combination of semi-Cayley graphs and generalized Cayley graphs. We study the isomorphisms and automorphisms of generalized semi-Cayley graphs and other related properties. [ABSTRACT FROM AUTHOR]

Let k, m and n be three positive integers such that 2m ≡ 1 (mod n) and k ≥ 2. The Bouwer graph, which is denoted by B(k, m, n), is the graph with vertex set { ( a ,   b ) ∣ a ∈ ℤ m ,   b ∈ ℤ n   ×   ⋯   ×   ℤ n ︸ k − 1   times } and two vertices being adjacent if they can be written as (a, b) and (a + 1, c), where either c = b or c = ( c 1 , c 2 , … , c k − 1 ) differs from b = ( b 1 , b 2 , … , b k − 1 ) in exactly one position, say the jth position, where c j = b j + 2 a . Every B(k, m, n) is a vertex- and edge-transitive graph, and Bouwer proved that B(k, 6, 9) is half-arc-transitive for every k ≥ 2. In 2016, Conder and Žitnik gave the classification of half-arc-transitive Bouwer graphs. In this paper, the full automorphism group of every B(k, m, n) is determined. [ABSTRACT FROM AUTHOR]

A Cayley graph Γ is called arc-transitive if its automorphism group AutΓ is transitive on the set of arcs in Γ. In this paper, we give a characterization of cubic arc-transitive Cayley graphs on a class of Frobenius groups. [ABSTRACT FROM AUTHOR]

Let be a subset of a commutative graded ring . The Cayley graph is a graph whose vertex set is and two vertices and are adjacent if and only if . The Cayley sum graph is a graph whose vertex set is and two vertices and are adjacent if and only if . Let be the set of homogeneous elements and be the set of zero-divisors of . In this paper, we study (total graph) and . In particular, if is an Artinian graded ring, we show that is isomorphic to a Hamming graph and conversely any Hamming graph is isomorphic to a subgraph of for some finite graded ring . [ABSTRACT FROM AUTHOR]

In 2011, Li et al. [The (strong) rainbow connection numbers of Cayley graphs on Abelian groups, Comput. Math. Appl.62(11) (2011) 4082–4088] obtained an upper bound of the strong rainbow connection number of an r-dimensional undirected toroidal mesh. In this paper, this bound is improved. As a result, we give a negative answer to their problem. [ABSTRACT FROM AUTHOR]

Let Sn denote the symmetric group of degree n with n ≥ 3, S = { cn = (1 2 ⋯ n), , (1 2)} and Γ n = Cay( Sn, S) be the Cayley graph on Sn with respect to S. In this paper, we show that Γ n ( n ≥ 13) is a normal Cayley graph, and that the full automorphism group of Γ n is equal to Aut(Γ n) = R( Sn) ⋊ 〈Inn( ϕ) ≅ Sn × ℤ2, where R( Sn) is the right regular representation of Sn, ϕ = (1 2)(3 n)(4 n−1)(5 n−2) ⋯ (∊ Sn), and Inn( ϕ) is the inner isomorphism of Sn induced by ϕ. [ABSTRACT FROM AUTHOR]

A Cayley graph is said to be core-free if is core-free in some for . A graph is called -regular if acts regularly on its -arcs. It is shown in this paper that if , then there exist no core-free tetravalent -regular Cayley graphs; and for , every tetravalent -regular Cayley graph is a normal cover of one of the three known core-free graphs. In particular, a characterization of tetravalent -regular Cayley graphs is given. [ABSTRACT FROM AUTHOR]

In this paper we determine all tetravalent Cayley graphs of a non-abelian group of order 3 p2, where p is a prime number greater than 3, and with a cyclic Sylow p-subgroup. We show that all of these tetravalent Cayley graphs are normal. The full automorphism group of these Cayley graphs is given and the half-transitivity and the arc-transitivity of these graphs are investigated. We show that this group is a 5-CI-group. [ABSTRACT FROM AUTHOR]

A graph is symmetric if its automorphism group acts transitively on the set of arcs of the graph. We classify connected heptavalent symmetric graphs of order 16 p for each prime p. As a result, there are two such sporadic graphs with p = 3 and 7, and an infinite family of 1-regular normal Cayley graphs on the group with 7|( p - 1). [ABSTRACT FROM AUTHOR]

The largest order of a Cayley graph of degree and diameter cannot exceed the Moore bound the asymptotic form of which is for and a fixed k. The second and the third author and the three authors proved by direct constructions that the Moore bound for diameter and , respectively, can be approached asymptotically by Cayley graphs in the sense that for some sequences of degrees . In this note we present a unifying principle underlying the two results, based on the existence of certain regular orbits of automorphism groups of suitable graphs. [ABSTRACT FROM AUTHOR]

We introduce cube-connected circulants as efficient models for communication networks. We give an algorithm for computing a shortest path between any pair of vertices in a cube-connected circulant. We give formulas for the diameter of a cube-connected circulant and the distance between any pair of vertices in such a graph. Then we give an embedding of cube-connected circulants into hypercubes, and an embedding of hypercubes into cube-connected circulants. We show cube-connected circulants outperform a few well-known network structures in several invariants. [ABSTRACT FROM AUTHOR]

In the degree-diameter problem for Abelian Cayley and circulant graphs of diameter 2 and arbitrary degree d there is a wide gap between the best lower and upper bounds valid for all d, being quadratic functions with leading coefficient 1/4 and 1/2 respectively. Recent papers have presented constructions which increase the coefficient of the lower bound to be at or just below 3/8 for sparse sets of degree d related to primes of specific congruence classes. The constructions use the direct product of the multiplicative and additive subgroups of a Galois field and a specific cyclic group of coprime order. It was anticipated that this approach would be capable of yielding further improvement towards the upper bound value of 1/2. In this paper, however, it is proved that the quadratic coefficient of the order of families of Abelian Cayley graphs of this class of construction can never exceed the value of 3/8, establishing an asymptotic limit of 3/8 for the quadratic coefficient of families of extremal graphs of this class. By applying recent results from number theory these constructions can be extended to be valid for every degree above some threshold, establishing an improved asymptotic lower bound approaching 3/8 for general Abelian Cayley and circulant graphs of diameter 2 and arbitrary degree d. [ABSTRACT FROM AUTHOR]

In this paper we determine all tetravalent Cayley graphs of a non-abelian group of order 3 p2, where p is a prime number greater than 3, and with a cyclic Sylow p-subgroup. We show that all of these tetravalent Cayley graphs are normal. The full automorphism group of these Cayley graphs is given and the half-transitivity and the arc-transitivity of these graphs are investigated. We show that this group is a 5-CI-group. [ABSTRACT FROM AUTHOR]

The adjacency spectrum of a graph is the multiset of eigenvalues of its adjacency matrix. Two graphs with the same spectrum are called cospectral. A graph is 'determined by its spectrum' (DS for short) if every graph cospectral to it is in fact isomorphic to it. A group is DS if all of its Cayley graphs are DS. A group is Cay-DS if every two cospectral Cayley graphs of are isomorphic. In this paper, we study finite DS groups and finite Cay-DS groups. In particular we prove that a finite DS group is solvable, and every non-cyclic Sylow subgroup of a finite DS group is of order , , or . We also give several infinite families of non-Cay-DS solvable groups. In particular we prove that there exist two cospectral non-isomorphic -regular Cayley graphs on the dihedral group of order for any prime . [ABSTRACT FROM AUTHOR]

For any positive integer , let denote the set of finite groups such that all Cayley graphs are integral whenever . Estélyi and Kovács [On groups all of whose undirected Cayley graphs of bounded valency are integral, Electron. J. Combin. 21 (2014) #P4.45.] classified for each . In this paper, we characterize the finite groups each of whose cubic Cayley graphs is integral. Moreover, the class is characterized. As an application, the classification of is obtained again, where . [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study a new class of Cayley graphs. [ABSTRACT FROM AUTHOR]

A classification of pentavalent symmetric graphs of order twice a prime square is given. It is proved that such a graph is a coset graph of ℤ3.6 (non-split extension), or a bi-coset graph of an extra-special group of order 125, or the standard double cover of a specific abelian Cayley digraph of order a prime square. [ABSTRACT FROM AUTHOR]

An infinite graph Γ is minor excluded if there is a finite graph that is not a minor of Γ. We prove that minor excluded graphs have finite Assouad-Nagata dimension and study minor exclusion for Cayley graphs of finitely generated groups. Our main results and observations are: (1) minor exclusion is not a group property: it depends on the choice of generating set; (2) a group with one end has a generating set for which the Cayley graph is not minor excluded; (3) there are groups that are not minor excluded for any set of generators, like ℤ3; (4) minor exclusion is preserved under free products; and (5) virtually free groups are minor excluded for any choice of finite generating set. [ABSTRACT FROM AUTHOR]

The concept of energy of a graph was first defined in 1978 by Gutman as the sum of the absolute values of the eigenvalues of its adjacency matrix. Let λ1, λ2, ..., λn be eigenvalues of graph Γ, then the Estrada index of Γ is defined as . The aim of this paper is to estimate the energy and Estrada index of Cayley graphs (G, S) where G ≅ D2n, U6n and S is a normal symmetric generating subset of G. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the Cayley graph of a partially ordered set (poset). Let (P, ≤) be a poset, and let S be a subset of P. We define the undirected Cayley graph of P, denoted by Cay(P, S), as a graph with vertex-set P and edge-set E consisting of those sets {x, y} such that y ∈ {x, s}ℓ or x ∈ {y, s}ℓ for some s ∈ S, where for a subset T of P, Tℓ is the set of all x ∈ P such that x ≤ t, for all t ∈ T. We study some basic properties of Cay(P, S) such as connectivity, diameter and girth. [ABSTRACT FROM AUTHOR]

There exist several generalizations of the classical Dirichlet convolution, for instance the so-called A-convolutions analyzed by Narkiewicz. We shall connect the concept of A-convolutions satisfying a weak form of regularity and Ramanujan sums with the spectrum of integral circulant graphs. These generalized Cayley graphs, having circulant adjacency matrix and integral eigenvalues, comprise a great amount of arithmetical features. By use of our concept we obtain a multiplicative decomposition of the so-called energy of integral circulant graphs with multiplicative divisor sets. This will be fundamental for the study of open problems, in particular concerning the detection of integral circulant graphs with maximal or minimal energy. [ABSTRACT FROM AUTHOR]

We introduce a property of geodesic metric spaces, called the road trip property, that generalizes hyperbolic and convex metric spaces. This property is shown to be invariant under quasi-isometry. Thus, it leads to a geometric property of finitely generated groups, also called the road trip property. The main result is that groups with the road trip property are finitely presented and satisfy a quadratic isoperimetric inequality. Examples of groups with the road trip property include hyperbolic, semihyperbolic, automatic and CAT(0) groups. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph with vertex set V(G) and edge set E(G). A function f : E(G) → {-1, 1} is called a signed star dominating function (SSDF) on G if ∑e∈E(v) f(e) ≥ 1 for every v ∈ V(G), where E(v) is the set of all edges incident to v. The signed star domination number of G is defined as γ(G) = {∑e∈E(G) f(e) | f G}. In this paper, we obtain exact values for the signed star domination number for certain classes of Cayley digraphs and Cayley graphs. [ABSTRACT FROM AUTHOR]

We generalise the Margolis-Meakin graph expansion of a group to a construction for ordered groupoids, and show that the graph expansion of an ordered groupoid enjoys structural properties analogous to those for graph expansions of groups. We also use the Cayley graph of an ordered groupoid to prove a version of McAlister's P-theorem for incompressible ordered groupoids. [ABSTRACT FROM AUTHOR]

The number theoretic analog of a net in metric geometry suggests new problems and results in combinatorial and additive number theory. For example, for a fixed integer g ≥ 2, the study of h-nets in the additive group of integers with respect to the generating set Ag = {0} ∪ {± gi : i = 0, 1, 2, ...} requires a knowledge of the word lengths of integers with respect to Ag. A g-adic representation of an integer is described that algorithmically produces a representation of shortest length. Additive complements and additive asymptotic complements are also discussed, together with their associated minimality problems. [ABSTRACT FROM AUTHOR]

A graph is one-regular if its automorphism group acts regularly on the set of its arcs. Let n be a square-free integer. It is shown in this paper that a pentavalent one-regular graph of order n exists if and only if n = 2 · 5tp1p2 ... ps ≥ 62, where t ≤ 1, s ≥ 1, and pi's are distinct primes such that 5|(pi-1). For such an integer n, there are exactly 4s-1 non-isomorphic pentavalent one-regular graphs of order n, which are Cayley graphs on dihedral groups constructed by Kwak et al. This work is a continuation of the classification of cubic one-regular graphs of order twice a square-free integer given by Zhou and Feng. [ABSTRACT FROM AUTHOR]

In this paper, we study the self-complementary Cayley graphs and count the number of isomorphic classes of undirected self-complementary circulants of order n, where n is square free. [ABSTRACT FROM AUTHOR]