On inverse problems for the cycle graph operator (Q1196567)

The cycle graph \(Cy(G)\) of a graph \(G\) has the set of all induced cycles of \(G\) as vertex set. Two distinct vertices are adjacent in \(Cy(G)\) whenever the corresponding cycles of \(G\) have at least one common edge. A graph \(H\) is called a cycle graph if there is some graph \(G\) such that \(H\simeq Cy(G)\). No characterization of cycle graphs is known up to now. In this paper, the following two partial characterizations are presented: (1) Among the graphs with maximum degree at most 3, cycle graphs can be described by forbidden induced subgraphs. These subgraphs are all cycles of length at least 4, and one additional graph. Note that, in particular, cycles of length at least 4 are no cycle graphs! (2) A graph containing no induced subgraph isomorphic to \(K_ 4-e\) is a cycle graph if and only if it is a block graph with every vertex lying in only finitely many blocks.