Lower and Upper Acyclicities on Unitary Cayley Graphs of Finite Commutative Rings

Abstract

A unitary Cayley graph $\Gamma_n$ of a finite cyclic ring $\mathbb{Z}_n$ is a graph with vertex set $\mathbb{Z}_n$ and two vertices $x$ and $y$ are adjacent if and only if $x-y$ is a unit in $\mathbb{Z}_n$ or equivalently, $\gcd(x-y,n)=1$. A nonempty subset $A$ of $\mathbb{Z}_n$  is called an acyclic set of $\Gamma_n$ if a subgraph of $\Gamma_n$ induced by $A$ contains no cycles. The maximum cardinality among the acyclic sets of $\Gamma_n$ is called the upper acyclic number of $\Gamma_n$ and is denoted by $\Lambda(\Gamma_n)$. Moreover, the maximum number $k$ of vertices of $\Gamma_n$ in which every subgraph of $\Gamma_n$ induced by $k$ vertices contains no cycles is called the lower acyclic number of $\Gamma_n$ and denoted by $\lambda(\Gamma_n)$. In this paper, we determine the lower and upper acyclic numbers for unitary Cayley graphs of $\mathbb{Z}_{n}$ and their complements.