Return to search

Characterizations of Trees With Equal Paired and Double Domination Numbers

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, and a double dominating set is a dominating set that dominates every vertex of G at least twice. We show that for trees, the paired-domination number is less than or equal to the double domination number, solving a conjecture of Chellali and Haynes. Then we characterize the trees having equal paired and double domination numbers.

Identiferoai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-19341
Date28 August 2006
CreatorsBlidia, Mostafa, Chellali, Mustapha, Haynes, Teresa W.
PublisherDigital Commons @ East Tennessee State University
Source SetsEast Tennessee State University
Detected LanguageEnglish
Typetext
SourceETSU Faculty Works

Page generated in 0.0019 seconds