Intersection-Representation by Connected Subgraphs of Some $n$-Cyclomatic Graph

Abstract

A hypergraph $H$ is called connected over a graph $G$ with the same vertex set as $H$ if every hyperedge of $H$ induces a connected subgraph in $G$. A graph $F$ is representable in the graph $G$ if there is some hypergraph $H$ which is connected over $G$ and has $F$ as its intersection graph. Generalizing the well-known problem of representability in forests, the following problems are investigated: Which hypergraphs are connected over some $n$-cyclomatic graph, and which graphs are representable in some $n$-cyclomatic graph, for any fixed integer $n$? Several notions developed in the theory of subtree hypergraphs and chordal graphs (i.e. in the case $n=0$) yield necessary or sufficient conditions, and in certain special cases even characterizations.