Title of article
NeST graphs Original Research Article
Author/Authors
Ryan B. Hayward، نويسنده , , Paul E. Kearney ، نويسنده , , Andrew Malton، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2002
Pages
15
From page
139
To page
153
Abstract
We establish results on NeST graphs (intersection tolerance graphs of neighborhood subtrees of a tree) and several subclasses. In particular, we show the equivalence of proper NeST graphs and unit NeST graphs, the equivalence of fixed distance NeST graphs and threshold tolerance graphs, and the proper containment of NeST graphs in weakly chordal graphs. The latter two results answer questions of Monma, Reed and Trotter, and Bibelnieks and Dearing.
Keywords
Unit NeST representation , Fixed tolerance NeST graph , Proper NeST graph , NeST graph , Tolerance graph , Interval graph , Weakly chordal graph , Threshold tolerance graph , Fixed distance NeST graph
Journal title
Discrete Applied Mathematics
Serial Year
2002
Journal title
Discrete Applied Mathematics
Record number
885431
Link To Document