Some notes on cycle graphs (Q1199489)

Let \(G\) be a finite, undirected graph without loops and multiple edges. Then the cycle graph \(C(G)\) of \(G\) is the graph whose vertices are the chordless cycles of \(G\), and two vertices in \(C(G)\) are adjacent whenever the corresponding chordless cycles have an edge in common. The {\(n\)-th} iterated cycle graph \(C^ n(G)\) of \(G\) is defined recursively by \(C^ n(G)=C(C^{n-1}(G))\) for \(n\geq 2\). \((C^ 0(G)=G\).) The main purpose of this paper is to correct a characterization of cycle-vanishing graphs given in \textit{S. V. Gervacio} [Graph theory, Proc. 1st Southeast Asian Colloq., Singapore 1983, Lect. Notes Math. 1073, 279-293 (1984; Zbl 0548.05036)], and \(G\) is said to be cycle-vanishing if there exists a nonnegative integer \(n\) such that \(C^ n(G)=\varnothing\). But first some notions in connection with paths are necessary. Two paths intercepted by a cycle \(C\) are parallel if they can be drawn in the interior of \(C\) so that they are internally disjoint and do not cross each other and they are said to be skew if they are disjoint but not parallel. A family of parallel paths intercepted by \(C\) let be denoted by \({\mathfrak P}\). Two parallel paths intercepted by \(C\) are said to be \(C\)-dependent if they are separated by some paths intercepted by \(C\), and a maximal family of \(C\)-dependent paths is called an ideal of \(C\). A path of order at least two in \(G\) is reflexive if its end vertices are adjacent in \(G\), otherwise it is irreflexive. A bundle \(B\) of reflexive (irreflexive) paths is a maximal set of reflexive (irreflexive) paths in \({\mathfrak P}\) with the same end vertices in \(C\) and the cardinality \(| B|\) is called the size of the bundle. Then the characterization is given by Theorem 3.1 whose proof of sufficiency is complete for a missing subcase in the former paper, but otherwise only outlined. A graph \(G\) of the form \(C\cup{\mathfrak P}\) is cycle-vanishing iff the following three properties are satisfied: (1) Any two irreflexive paths of \({\mathfrak P}\) are separated by at least two chords in \({\mathfrak P}\) in bundles of size one; (2) Any ideal of \(C\) consisting of at least four paths contains only reflexive paths; (3) Each edge of \(G\) lies in at most three chordless cycles. A more general characterization for any \(G\) is given by Theorem 3.2: \(G\) is cycle-vanishing iff the following holds: (1) \(G\) does not contain a cycle intercepting two skew paths; (2) \(G\) does not contain an edge belonging to at least four chordless cycles; (3) For every subgraph of \(G\) which consists of a cycle \(C\) and a maximal family \({\mathfrak P}\) properties (1) and (2) of Theorem 3.1 must hold.