Intersection graphs of concatenable subtrees of graphs (Q1331898): Difference between revisions

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.