On Cycle Graphs

Abstract

The cycle graph $C(G)$ of a graph $G$ has vertices which correspond to the chordless cycles of $G$, and two vertices of $C(G)$ are adjacent if the corresponding chordless cycles of $G$ have at least one edge in common. If $G$ has no cycle, then we define $C(G)=\mathrm{\varnothing }$, the empty graph. For an integer $n\ge 2$, we define recursively the $n$-th iterated cycle graph $C^n(G)$ by $C^n(G)=C(C^{n-1}(G))$. We classify graphs according to their cycle graphs as follows. A graph $G$ is \emph{cycle-vanishing} if there exists an integer $n$ such that $C^n(G)=\mathrm{\varnothing }$; and $G$ is \emph{cycle-periodic} if there exist two integers $n$ and $p\ge 1$ such that $C^{n+p}(G)\cong C^n(G)\ne \mathrm{\varnothing }$. Otherwise, $G$ is cycle-expanding. We characterize these three types of graphs, and give some other results on cycle graphs.