On inverse problems for the cycle graph operator
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.
- Some notes on cycle graphs
- Inverse problems on a graph with loops
- Characterization of Cycle Stochastic Graphs
- Cycle stochastic graphs: structural and forbidden graph characterizations
- Cycle intersection graphs and minimum decycling sets of even graphs
- Inverse Problems and Zero Forcing for Graphs
- scientific article; zbMATH DE number 969988 (Why is no real title available?)
- On the cycle‐isomorphism of graphs
- Spectrum of cycle graphs of some graphs
- On cycle graphs
This page was built for publication: On inverse problems for the cycle graph operator
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1196567)
