Intersection graphs of concatenable subtrees of graphs

DOI10.1016/0166-218X(94)90081-7MaRDI QIDQ1331898zbMATH OpenOpenAlexFDO

Publication date 26 January 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(94)90081-7

acanthus clique concatenable subtrees directed cycles directed subtree fraternal orientation Helly family intersection graph polynomial time algorithms rooted subtree

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

Let \(G = G(V,E)\) be a finite, simple (directed or undirected) graph. A free subtree \(t\) of an undirected graph \(G\) is an acyclic connected edge subgraph of \(G\). Is a particular vertex \(r\) of \(t\) marked as root, \(t\) is called rooted subtree or simply subtree. A directed subtree is a rooted subtree having its edges oriented from the root towards the terminal vertices. Two subtrees are called concatenable if either they are disjoint or their intersection contains the root of them and their union contains no cycle. An acanthus is a graph which is a free tree or is obtained by adding an edge to a free tree (a directed acanthus is defined analogously). An orientation of a graph is called fraternal if for every three vertices \(u, v, w\) the existence of the edges \(u \to w\) and \(v \to w\) implies that \(u\) and \(v\) are adjacent. The set containing a vertex \(v\) and its adjacent vertices (neighborhood) is denoted by \(\Gamma v\); is \(v\) from a directed graph, then the sets \(\{u \mid u \to v\}\) and \(\{u \mid v \to u\}\) are denoted \(\Gamma^{in}v\) and \(\Gamma^{out} v\), respectively. A clique \(U\) is a clique cut-set if \(G(V-U)\) is not connected. And finally a family of subtrees \(S\) of a graph \(G\) is called a Helly family if every subfamily in which every two subtrees have a nonempty intersection, has a nonempty intersection. The present paper is a very extensive one with many lemmas and corollaries, so that here the results are given from the introduction of the paper: Consider a family \(S\) of pairwise concatenable subtrees of an undirected graph \(H\) and assume that its intersection graph \(G\) is connected. In Theorem 2.5 we prove that the subgraph of \(H\) obtained by the union of the subtrees in \(S\) is an acanthus. Therefore, a connected graph is the intersection graph of a family of pairwise concatenable subtrees of an undirected graph iff it is the intersection graph of a family of pairwise concatenable subtrees of an acanthus. In Theorems 3.3 and 3.4 we prove that a connected graph \(G\) is the intersection graph of a family of pairwise concatenable subtrees of an acanthus iff it has a fraternal orientation in which for every vertex \(v\), both \(G(\Gamma^{in}v)\) and \(G(\Gamma^{out}v)\) have no directed cycles. In Theorem 3.6 we prove that \(G\) is an intersection graph of a Helly family of pairwise concatenable subtrees of an acanthus iff it has a fraternal orientation such that for every vertex \(v\) of \(G\), \(G(\Gamma v)\) has no directed cycles. In Section 4 we give a characterization by clique cut-set decompositions of the intersection graphs of families of pairwise concatenable subtrees of undirected acanthae. Using it, we describe polynomial time algorithms for solving various problems related to these intersection graphs.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Intersection graphs of concatenable subtrees of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1331898)