NeST graphs (Q1613397)

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.