THE NEIGHBORHOOD INCLUSION STRUCTURE OF A GRAPH

Motivated by connections with problems in network reliability, we expl ore the relationship between vertex neighborhoods N(u) in a graph, foc using on neighborhood equality and inclusion (suitably modified for ad jacent vertices). We survey recent work which shows that solutions to certain reliability extremal problems must be graphs in which the neig hborhood inclusion relation is total; such graphs are known in the lit erature as threshold graphs. We then define a mixed graph M(G) determi ned by the neighborhood inclusion relation on the vertices of a graph G and also a digraph D(G) obtained from M(G) by identifying points wit h the ''same'' neighborhood in G. We characterize M(G) and D(G) for th reshold graphs and for trees.