Nordhaus-Gaddum Inequalities for Domination in Graphs
Document Type
Article
Publication Date
8-1-1996
Description
A node in a graph G = (V,E) is said to dominate itself and all nodes adjacent to it. A set S ⊂ V is a dominating set for G if each node in V is dominated by some node in S and is a double dominating set for G if each node in V is dominated by at least two nodes in S. First we give a brief survey of Nordhaus-Gaddum results for several domination-related parameters. Then we present new inequalities of this type involving double domination. A direct result of our bounds for double domination in complementary graphs is a new Nordhaus-Gaddum inequality for open domination improving known bounds for the case when both G and its complement have domination number greater than 4.
Citation Information
Harary, Frank; and Haynes, Teresa W.. 1996. Nordhaus-Gaddum Inequalities for Domination in Graphs. Discrete Mathematics. Vol.155(1-3). 99-105. https://doi.org/10.1016/0012-365X(94)00373-Q ISSN: 0012-365X