The neighborhood inclusion structure of a graph (Q1310225)

Some problems related to the network reliability lead to the exploration of the relationship between vertex neighborhoods \(N_ u\) in a graph. Authors define neighborhood equivalence relation \(\equiv_ N\) and neighborhood relation \(<_ N\). If every pair of vertices of \(G\) is related by the \(\leq_ N\) relation, the graph \(G\) is called a treshold graph. In the first part of the paper authors show that the solution of two extremal problems in networks can be described in terms of threshold graphs. In the second part of the paper are discussed properties of the inclusion mixed graph \(M(G)\) of \(G\), the reduced inclusion digraph \(D(G)\) of \(G\) and the neighborhood reduction \(\rho_ N (G)\) of \(G\). \(M(G)\) has a directed edge from \(u\) to \(v\) iff \(u<_ N v\), and has an undirected edge between \(u\) and \(v\) iff \(u \equiv_ N v\). \(D(G)\) is obtained from \(M(G)\) by contracting the maximal complete undirected subgraphs to points. \(\rho_ N (G)\) is obtained from \(G\) by a sequence of quotients by the relation \(\equiv_ N\). Authors characterize the threshold graphs in terms of \(M(G)\), \(D(G)\) and \(\rho_ N (G)\).