Abstract
A paired-dominating set of a graph is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph. Recently, Chen et al. (Acta Math Sci Ser A Chin Ed 27(1):166-170, 2007) proved that a cubic graph has paired-domination number at most three-fifths the number of vertices in the graph. In this paper, we show that the Petersen graph is the only connected cubic graph with paired-domination number three-fifths its order.
| Original language | English |
|---|---|
| Pages (from-to) | 675-692 |
| Number of pages | 18 |
| Journal | Graphs and Combinatorics |
| Volume | 25 |
| Issue number | 5 |
| DOIs | |
| Publication status | Published - Feb 2010 |
Keywords
- Bounds
- Cubic graphs
- Paired-domination
- Petersen graph
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics