Abstract
Let G = (V, E) be a simple connected graph. A set S ⊂ V is called a paired-dominating set if every vertex in V \ S has at least one neighbor in S and the subgraph induced by 5 contains a perfect matching. The paired-domination number of G, denoted by γPr(G), is the minimum cardinality of a paired-dominating set of G. We prove that a claw-free graph G with δ(G) ≥ 4 contains a paireddominating set with cardinality at most one half of its order and the bound is sharp. This result improves the result in [X.G. Cao, E.F. Shan, Paired-domination in claw-free graphs with minimum degree at least four, Ars Combinatoria. 127(2016) 401-408.].
| Original language | English |
|---|---|
| Pages (from-to) | 393-409 |
| Number of pages | 17 |
| Journal | Ars Combinatoria |
| Volume | 139 |
| State | Published - Jul 2018 |
Keywords
- Claw-free graph
- Domination
- Paired-domination