Premium
Vertex domination‐critical graphs
Author(s) -
Brigham Robert C.,
Chinn Phyllis Z.,
Dutton Ronald D.
Publication year - 1988
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230180304
Subject(s) - dominating set , vertex (graph theory) , combinatorics , domination analysis , neighbourhood (mathematics) , mathematics , graph , discrete mathematics , mathematical analysis
A dominating set in a graph G is a set of vertices D such that every vertex of G is either in D or is adjacent some vertex of D. The domination number Γ( G ) of G is the minimum cardinality of any dominating set. A graph is vertex domination‐critical if the removal of any vertex decreases its domination number. This paper gives examples and properties of vertex domination‐critical graphs, presents a method of constructing them, and poses some open questions. In the process several results for arbitrary graphs are presented.