Structural and spectral properties of addition cayley graphs

Abstract

Cayley graph was introduced for finite groups by Arthur Cayley in 1878. Cayley newline newlinegraph encodes the abstract structure of a graph. In 1969, Lovasz proposed a con- newlinejecture, every connected vertex transitive graph contains a Hamiltonian path. The newline newlineadvantage of the Cayley graph formulation is that it provides a discrete representation newlinefor a finite group G together with a generating set S. Thus, one can ask for which newlineG and S, the conjecture holds rather than attack it in full generality. A new variant newlineof the Cayley graph namely, addition Cayley graph was introduced in 2003. Unitary newlineaddition Cayley graph is an addition Cayley graph on Zn together with generating newlineset Un. newline newlineThis work is an attempt to study irregular Cayley graphs and its graph invari- newlineants such as independence number, chromatic number, clique number, connectivity newline newlineand diameter. It is shown that unitary addition Cayley graph Gn is perfect if and newlineonly if n is even or n = p newline newlinem, m and#8805; 1. Spectral properties such as eigenvalues, Lapla- newlinecian eigenvalues, signless Laplacian eigenvalues of unitary addition Cayley graphs and newline newlinetheir complement are discussed. Bounds for the energy, Laplacian energy and signless newline newlineLaplacian energy for unitary addition Cayley graphs and their complements are com- newlineputed. It is also shown that unitary addition Cayley graph Gn is hyperenergetic if newline newlineand only if n is odd other than the prime number and power of 3 or n is even and has newline newlineat least three distinct prime factors. It is proved that the complement of Gn is hyper- newlineenergetic if and only if n has at least two distinct prime factors and n 6= 2p. Bounds newline newlineon distance spectrum, distance signless Laplacian spectrum and distance Laplacian newlineenergy of unitary addition Cayley graphs are obtained. newline