Constant tolerance intersection graphs of subtrees of a tree
type: Item
instance of: scholarly article
title: Constant tolerance intersection graphs of subtrees of a tree
zbMATH Open document ID: 1061.05079
author: Robert E. Jamison
author: Henry Martyn Mulder
published in: Discrete Mathematics
publication date: 2005-02-22T00:00:00Z
review text: Let \(G= (V,E)\) be a connected, finite, simple and loopless graphs. In this paper the structure of the intersection of a family of subsets of a set is investigated: the vertices of the graph are represented by the subsets of the family and adjacency is defined by a non-empty intersection of the corresponding subsets. Prime examples are interval graphs and chordal graphs, and a known classical result is the characterization of interval graphs by forbidden subgraphs. The authors generalize this by using tolerances introduced by Golumbic and Monma: each representing interval is assigned a positive real number, its tolerance, and two vertices are adjacent if the length of the intersection of their corresponding intervals exceeds the minimum of the two tolerances. This idea was used to formulate tolerance intersection graphs by the authors where \(G= (V,E)\) may be represented by a host tree \(T\) together with a family \(\{S_v\}_{v\in V}\) of subtrees of \(T\) and a tolerance \(t\) such that \(uv\in E\) iff \(|S_u\cap S_v|\geq t\). Then \(G\) has an \((h,s,t)\)-representation if moreover there exists a maximum degree of \(T\) at most \(h\) and a maximum degree of all \(S_v\subset T\) of at most \(s\). If no restrictions are imposed on \(h\), it is written \(h=\infty\), similarly it is written \(s= \infty\). In Section 2 concepts are introduced which are used in the paper. An example let be given here: If \(G_1\) and \(G_2\) and are two graphs with non-empty intersection \(G_1\cap G_2\), then \(G_1\cup G_2= (V_1\cup V_2, E_1\cup E_2)\) is the amalgamation of \(G_1\) and \(G_2\) along the common subgraph \(G_1\cap G_2\) (we also say: the amalgamation along the set of common vertices \(V_1\cap V_2\)). Furthermore, in Section 2 various kinds of representations are introduced and already known results from the literature are mentioned. (The class of \((h,s,t)\)-graphs is denoted by \([h,s,t]\) and being an \((h,s,t)\)-graph is a hereditary property which raises the problem …
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 2137020
zbMATH Keywords: Intersection graph
zbMATH Keywords: Tolerance
zbMATH Keywords: Chordal graph
zbMATH Keywords: \(k\)-simplicial vertex
zbMATH Keywords: Subtree representation
zbMATH Keywords: Regular tree
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: j.disc.2004.04.017
OpenAlex ID: W2068177175
cites work: A characterisation of rigid circuit graphs
cites work: On rigid circuit graphs
cites work: Intersection representation of complete unbalanced bipartite graphs
cites work: Onp-intersection representations
cites work: Set intersection representations for almost all graphs
cites work: Graphs of small dimensions
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Q3328583
cites work: The edge intersection graphs of paths in a tree
cites work: Edge and vertex intersection of paths in a tree
cites work: Q3322150
cites work: Tolerance graphs
cites work: Q4873748
cites work: Alternating Whitney sums and matchings in trees. 1
cites work: Alternating Whitney sums and matchings in trees. II
cites work: Tolerance intersection graphs on binary trees with constant tolerance 3
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Sur deux propriétés des classes d'ensembles
cites work: Topics in Intersection Graph Theory
cites work: Connectivity threshold for random chordal graphs
cites work: Intersection graphs of paths in a tree
cites work: Triangulated edge intersection graphs of paths in a tree
cites work: Representations of chordal graphs as subtrees of a tree
cites work: Q4869540
DOI: 10.1016/J.DISC.2004.04.017
description: scientific article; zbMATH DE number 2137020