On inverse problems for the cycle graph operator (Q1196567)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On inverse problems for the cycle graph operator |
scientific article |
Statements
On inverse problems for the cycle graph operator (English)
0 references
16 January 1993
0 references
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.
0 references
edge intersection graphs
0 references
graph-valued functions
0 references
cycle graph
0 references
characterization
0 references
induced subgraphs
0 references
block graph
0 references