Search

Circulant graphs are useful networks because of their symmetries. For k ⩾ 2 and n ⩾ 2 k + 1 , the circulant graph C n (1 , 2 , ... , k) consists of the vertices v 0 , v 1 , v 2 , ... , v n - 1 and the edges v i v i + 1 , v i v i + 2 , ... , v i v i + k , where i = 0 , 1 , 2 , ... , n - 1 , and the subscripts are taken modulo n. The metric dimension β (C n (1 , 2 , ... , k)) of the circulant graphs C n (1 , 2 , ... , k) for general k (and n) has been studied in several papers. In 2017, Chau and Gosselin proved that β (C n (1 , 2 , ... , k)) ⩾ k for every k , and they conjectured that if n = 2 k + r , where k is even and 3 ⩽ r ⩽ k - 1 , then β (C n (1 , 2 , ... , k)) = k. We disprove both by showing that for every k ⩾ 9 , there exists an n ∈ [ 2 k + 5 , 2 k + 8 ] ⊂ [ 2 k + 3 , 3 k - 1 ] such that β (C n (1 , 2 , ... , k)) ⩽ 2 k 3 + 2. We conjecture that for k ⩾ 6 , β (C n (1 , 2 , ... , k)) cannot be less than 2 k 3 + 2. [ABSTRACT FROM AUTHOR]

The topological properties of graphs are well studied. More specifically the genus of graphs and their embeddings are attractions to many authors. In this survey, we present the results concerning the genus of total graph and generalized the total graph and generalized total graphs of commutative rings. [ABSTRACT FROM AUTHOR]

We study the following conjecture of Matt DeVos: If there is a graph homomorphism from Cayley graph Cay( M , B ) to another Cayley graph Cay( M ′ , B ′ ) then every graph with ( M , B )-flow has ( M ′ , B ′ )-flow. This conjecture was originally motivated by the flow-tension duality. We show that a natural strengthening of this conjecture does not hold in all cases but we conjecture that it still holds for an interesting subclass of them and we prove a partial result in this direction. We also show that the original conjecture implies the existence of oriented cycle double cover with a small number of cycles. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A . The transition matrix corresponding to G is defined by H ( t ) : = exp ⁡ ( i t A ) , t ∈ R . The graph G is said to have perfect state transfer (PST) from a vertex u to another vertex v , if there exist τ ∈ R such that the uv -th entry of H ( τ ) has unit modulus. The graph G is said to be periodic at τ ∈ R if there exist γ ∈ C with | γ | = 1 such that H ( τ ) = γ I , where I is the identity matrix. A gcd -graph is a Cayley graph over a finite abelian group defined by greatest common divisors. In this paper, we construct classes of gcd -graphs having periodicity and perfect state transfer. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with two binary operators addition (+) and multiplication (.). Then Z n is a ring of integers modulo n , where n is a positive integer. A Absorption Cayley graph denoted by Ω ( Z n ) is a graph whose vertex set is Z n , the integer modulo n and edge set E = { a b : a + b ∈ S } , where S = { a ∈ Z n : a b = b a = a for any b ∈ Z n , b ≠ a , b ≠ 1 } . Here a b = a is the absorption property as b is absorbed in a . We study the characterization of Absorption cayley graphs along with its properties such as connectedness, degree, diameter, planarity, girth, regularity. [ABSTRACT FROM AUTHOR]

Motivated by an open problem of Abawajy et al. [1] we find some relations between power graphs and Cayley graphs of finite cyclic groups. We show that the vertex deleted subgraphs of some power graphs are spanning subgraphs or equal to the complement of vertex deleted subgraphs of some unitary Cayley graphs. Also we prove that some Cayley graphs can be expressed as direct product of power graphs. Applying these relations we study the eigenvalues and energy of power graphs and the related Cayley graphs. [ABSTRACT FROM AUTHOR]

The research on deterministic small-world network model is an important branch of complex network modeling. This paper analyzes the small-world property of the minimal Cayley graph and proposes a deterministic small-world network model based on minimal Cayley graph. The model constructs a class of small-world networks with high symmetry by selecting a minimal Cayley graph, and appropriately expands its generating set. Compared with the existing models, this model can be used flexibly to get small-world networks with const degree or variable degree, which is adaptable for the design and analysis of the real networks such as communication network and P2P overlay network. [ABSTRACT FROM AUTHOR]

Abstract: An antimagic labeling of a finite simple undirected graph with q edges is a bijection from the set of edges to the set of integers such that the vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of labels of all edges incident to such vertex. A graph is called antimagic if it admits an antimagic labeling. It was conjectured by N. Hartsfield and G. Ringel in 1990 that all connected graphs besides are antimagic. Another weaker version of the conjecture is every regular graph is antimagic except . Both conjectures remain unsettled so far. In this article, we focus on antimagic labeling of regular graphs. Certain classes of regular graphs with particular factors are shown to be antimagic. Note that the results here are also valid for regular multi-graphs. [Copyright &y& Elsevier]

Abstract: Denote by the number of cliques of order t in a graph G having n vertices. Let where denotes the complement of G. Let and be the limit of for n going to infinity. A 1962 conjecture of Erdős stating that was disproved by Thomason in 1989 for all . Tighter counterexamples have been constructed by Jagger, Šťovíček and Thomason in 1996, by Thomason for in 1997, and by Franek for in 2002. We investigate a computational framework to search for tighter upper bounds for small t and provide the following improved upper bounds for and 8: , , and . The constructions are based on a large but highly regular variant of Cayley graphs for which the number of cliques and cocliques can be expressed in closed form. Note that if we consider the quantity , the new upper bound of 0.687 for is the first bound for any smaller than the lower bound of 0.695 for due to Giraud in 1979. [Copyright &y& Elsevier]

Both the pancake graph and star graph are Cayley graphs and are especially attractive for parallel processing. They both have sublogarithmic diameter, and are fairly sparse compared to hypercubes. In this paper, we focus on another important property, namely the genus. The genus of a graph is the minimum number of handles needed for drawing the graph on the plane without edges crossing. We will investigate the upper bound and lower bound for the genus of pancake graph and compare these values with the genus of the star graph as well as that of the hypercube. [ABSTRACT FROM AUTHOR]

Abstract: A (k, g)-cage is a k-regular graph of girth g of minimum order. While many of the best known constructions of small k-regular graphs of girth g are known to be Cayley graphs, no general theory of the relation between the girth of a Cayley graph and the structure of the underlying group has been developed. We attempt to fill the gap by focusing on the girths of Caley graphs of nilpotent and solvable groups, and present a series of results supporting the intuitive idea that the closer a group is to being abelian, the less suitable it is for constructing Cayley graphs of large girths. Specifically, we establish the existence of upper bounds on the girths of Cayley graphs with respect to the nilpotency class and/or the length of the derived sequence of the underlying groups. [Copyright &y& Elsevier]

Abstract: An anticoloring of a graph is a coloring of some of the vertices, such that no two adjacent vertices are colored in distinct colors. We deal with the anticoloring problem with two colors, in the particular cases of graphs which are strong products of two paths or two cycles, and provide an explicit optimal solution. [Copyright &y& Elsevier]

Abstract: We present an upper bound on the number of vertices in graphs of given degree and diameter 3 that arise as lifts of dipoles with voltage assignments in Abelian groups. Further, we construct a family of Cayley graphs of degree and diameter of order . By comparison with other available results in this area we show that, for sufficiently large d and k such that , our family gives the current largest known Cayley graphs of degree d and diameter k. [Copyright &y& Elsevier]

Abstract: A rough structure theorem for small separations in symmetric graphs is developed. Let be a vertex transitive graph, let be finite with set for some . We show that whenever the diameter of G is at least , either , or G has a (bounded) ring-like structure and A is efficiently contained in an interval. This theorem has applications to the study of product sets and expansion in groups. [Copyright &y& Elsevier]

A graph is perfect if each of its induced subgraphs H has the property that its chromatic number χ(H) equals its clique number ω(H). The Strong Perfect Graph Conjecture (SPGC) states: An undirected graph is perfect if and only if neither G nor its complement G contains, as an induced subgraph, a chordless cycle whose length is odd and at least 5. In this paper we show that SPGC holds for minimal Cayley graphs. Let G be a finite group and S a generating set for G with e ∉ S, and if s ∈ S, then s-1 ∈ S. The Cayley graph determined by the pair (G, S), and denoted by Γ(G, S), is the graph with vertex set V(Γ) consisting of the following elements: (x, y) ∈ E(Γ) if and only if x-1y ∈ S. A Cayley graph is minimal if no proper subset of its generating set also generates G.We also give a sufficient condition for Cayley graphs derived from permutation groups to be perfect, prove that certain P2, C3 factorizations yield perfect general graphs, and identify families of perfect Cayley graphs. [Copyright &y& Elsevier]