The Mapping $\overline{C}:G\to C(\overline{G})$ a New Graph Theoretic Map

Abstract

The cycle graph $C(H)$ of a graph $H$ is the edge intersection graph of all induced chordless cycles of $H$. We investigate iterates of the mapping $\overline{C}:G\to C(\overline{G})$ where $C$ denotes the map that associates to a graph its cycle graph. We call a graph $G$ vanishing under $\overline{C}$ if $\overline{C^n}(G)=0$ for some $n$, otherwise $G$ is called $\overline{C}$-persistent. We call a graph $G$ expanding under $\overline{C}$ if $|\overline{C^n}(G)|\to \mathrm{\infty }$ as $n\to \mathrm{\infty }$. We show that the lowest order of a $\overline{C}$-expanding graph is $6$ and determine the behaviour under $\overline{C}$ of some special graphs, including trees, null graphs, cycles and complete bipartite graphs.