NeST graphs
type: Item
instance of: scholarly article
title: NeST graphs
zbMATH Open document ID: 1003.05087
DOI: 10.1016/S0166-218X(01)00207-4
author: Ryan Hayward
author: Paul Kearney
author: Andrew J. Malton
published in: Discrete Applied Mathematics
publication date: 2002-08-29T00:00:00Z
review text: Let all graphs \(G= (V,E)\) considered in the paper be simple and undirected ones. \(G\) is a generalization of the known interval graph if there is a set \(\{I_v\mid v\in V\}\) of intervals of the real line and a set \(\{\tau_v\mid v\in V\}\) of positive tolerances such that \(xy\in E\) iff \(|I_x\cap I_y|\geq \min\{\tau_x,\tau_y\}\). Such a graph \(G\) is called a tolerance graph. And by replacing neighborhoods of the line (namely intervals) with neighborhoods of an embedded tree this generalization of the tolerance graph yields the class of neighborhood subtree tolerance (NeST) graphs (see the exact Definition 1). In the present paper properties of NeST graphs are investigated and especially the following four subclasses are considered: (1) unit NeST graphs, in which all neighborhood subtrees have unit diameter; (2) proper NeST graphs, in which no neighborhood subtree is properly contained in another; (3) fixed distance NeST graphs, in which neighborhood subtree centers are equidistant; (4) fixed tolerance NeST graphs, in which all tolerances are the same. Besides numerous detailed results the authors get the following main results which partly are equivalence relations: (1) \(G\) is a proper NeST graph iff \(G\) is a unit NeST graph (Theorem 2). (2) \(G\) is a fixed distance NeST graph iff \(G\) is a threshold tolerance graph (Theorem 7). (3) \(G\) is a threshold graph iff it is a fixed tolerance, fixed distance NeST graph (Theorem 8). (4) It is known that NeST graphs are weakly chordal (i.e. neither the graph nor its complement contains an induced cycle with five or more vertices), but the authors could show that there exists a class of weakly chordal graphs which are not NeST (e.g. the 2-star, 3-star and 4-star; see figure in the paper). The authors prove that NeST graphs form a proper subclass of the weakly chordal graphs (Lemma 6). Finally three open problems are given.
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1792339
zbMATH Keywords: interval graph
zbMATH Keywords: tolerance graph
zbMATH Keywords: neighborhood subtree tolerance
zbMATH Keywords: threshold graph
zbMATH Keywords: chordal graphs
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Topics on perfect graphs
cites work: Neighborhood subtree tolerance graphs
cites work: Proper and unit tolerance graphs
cites work: Q3097395
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: A recognition algorithm for the intersection graphs of paths in trees
cites work: Q3328583
cites work: Edge and vertex intersection of paths in a tree
cites work: Q3216686
cites work: Q3322150
cites work: Tolerance graphs
cites work: Q4828541
cites work: Weakly triangulated graphs
cites work: Tolerance intersection graphs on binary trees with constant tolerance 3
cites work: Threshold tolerance graphs
cites work: Q5588432
cites work: A Class of Balanced Matrices Arising from Location Problems
full work available at URL: s0166-218x(01)00207-4
OpenAlex ID: W2914372882
description: scientific article; zbMATH DE number 1792339