Intersection graphs of concatenable subtrees of graphs
type: Item
instance of: scholarly article
title: Intersection graphs of concatenable subtrees of graphs
zbMATH Open document ID: 0805.05068
DOI: 10.1016/0166-218X(94)90081-7
published in: Discrete Applied Mathematics
publication date: 1995-01-26T00:00:00Z
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. I…
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 626256
zbMATH Keywords: directed subtree
zbMATH Keywords: rooted subtree
zbMATH Keywords: acanthus
zbMATH Keywords: clique
zbMATH Keywords: Helly family
zbMATH Keywords: concatenable subtrees
zbMATH Keywords: intersection graph
zbMATH Keywords: fraternal orientation
zbMATH Keywords: directed cycles
zbMATH Keywords: polynomial time algorithms
author: Fanica Gavril
author: J. Urrutia
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Algorithms on circular-arc graphs
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Q3328583
cites work: Q5597453
cites work: Intersection graphs of paths in a tree
cites work: Q3291034
cites work: Q4138414
cites work: Triangulated graphs and the elimination process
cites work: An Efficient Test for Circular-Arc Graphs
cites work: An algorithm for fraternal orientation of graphs
full work available at URL: 0166-218x(94)90081-7
OpenAlex ID: W2000918288
description: scientific article; zbMATH DE number 626256