Edge criticality in graph domination
JH van Vuuren - Graphs and Combinatorics, 2016 - Springer
JH van Vuuren
Graphs and Combinatorics, 2016•SpringerA vertex subset D ⊆ VD⊆ V of a graph G=(V, E) G=(V, E) is a dominating set of G if each
vertex of G is a member of D or is adjacent to a member of D. The cardinality of a smallest
dominating set of G is called the domination number of G and a nonempty graph G is q-
critical if q is the smallest number of arbitrary edges of G whose removal from G necessarily
increases the domination number of the resulting graph. The classes of q-critical graphs of
order n are characterised in this paper for all admissible combinations of values of n and q.
vertex of G is a member of D or is adjacent to a member of D. The cardinality of a smallest
dominating set of G is called the domination number of G and a nonempty graph G is q-
critical if q is the smallest number of arbitrary edges of G whose removal from G necessarily
increases the domination number of the resulting graph. The classes of q-critical graphs of
order n are characterised in this paper for all admissible combinations of values of n and q.
Abstract
A vertex subset of a graph is a dominating set of G if each vertex of G is a member of D or is adjacent to a member of D. The cardinality of a smallest dominating set of G is called the domination number of G and a nonempty graph G is q-critical if q is the smallest number of arbitrary edges of G whose removal from G necessarily increases the domination number of the resulting graph. The classes of q-critical graphs of order n are characterised in this paper for all admissible combinations of values of n and q.
Springer
Showing the best result for this search. See all results