The neighborhood inclusion structure of a graph
type: Item
instance of: scholarly article
title: The neighborhood inclusion structure of a graph
zbMATH Open document ID: 0795.05119
DOI: 10.1016/0895-7177(93)90248-W
author: Ralph Tindell
author: Frank Harary
author: F. T. Boesch
author: Charles L. Suffel
published in: Mathematical and Computer Modelling
publication date: 1994-09-11T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 475035
zbMATH Keywords: vertex neighborhoods
zbMATH Keywords: treshold graph
zbMATH Keywords: inclusion mixed graph
zbMATH Keywords: reduced inclusion digraph
zbMATH Keywords: neighborhood reduction
MaRDI profile type: Publication
cites work: Q3328583
cites work: The number of spanning trees in a prism
cites work: Graphs with maximal number of adjacent pairs of edges
cites work: The spanning subgraphs of eulerian graphs
full work available at URL: 0895-7177(93)90248-w
OpenAlex ID: W2027278805
description: scientific article; zbMATH DE number 475035