Abstract
A vertex in G is said to dominate itself and its neighbors. A subset S of vertices is a dominating set if S dominates every vertex of G. A paired-dominating set is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by γ pr(G), is the minimum cardinality of a paired-dominating set in G. A subset S⊆V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ ×2(G). A claw-free graph is a graph that does not contain K 1,3 as an induced subgraph. Chellali and Haynes (Util. Math. 67:161–171, 2005) showed that for every claw-free graph G, we have γ pr(G)≤γ ×2(G). In this paper we extend this result by showing that for r≥2, if G is a connected graph that does not contain K 1,r as an induced subgraph, then \(\gamma_{\mathrm{pr}}(G)\le ( \frac{2r^{2}-6r+6}{r(r-1)} )\gamma_{\times2}(G)\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Blidia M, Chellali M, Haynes TW (2006) Characterizations of trees with equal paired and double domination numbers. Discrete Math 306:1840–1845
Brešar B, Henning MA, Rall DF (2007) Paired-domination of Cartesian products of graphs. Util Math 73:255–265
Chellali M, Haynes TW (2005) On paired and double domination in graphs. Util Math 67:161–171
Chen XG, Shiu WC, Chan WH (2008) Upper bounds on the paired-domination number. Appl Math Lett 21:1194–1198
Dorbec P, Gravier S (2008) Paired-domination in P 5-free graphs. Graphs Comb 24:303–308
Dorbec P, Gravier S (2010) Paired-domination in subdivided star-free graphs. Graphs Comb 26:43–49
Dorbec P, Gravier S, Henning MA (2007) Paired-domination in generalized claw-free graphs. J Comb Optim 14:1–7
Favaron O, Henning MA (2004) Paired-domination in claw-free cubic graphs. Graphs Comb 20:447–456
Harant J, Henning MA (2008) A realization algorithm for double domination in graphs. Util Math 76:11–24
Harary F, Haynes TW (2000) Double domination in graphs. Ars Comb 55:201–213
Haynes TW, Slater PJ (1995) Paired-domination and the paired-domatic number. Congr Numer 109:65–72
Haynes TW, Slater PJ (1998) Paired-domination in graphs. Networks 32:199–206
Haynes TW, Hedetniemi ST, Slater PJ (1998) Fundamentals of domination in graphs. Marcel Dekker, New York
Liao CS, Chang GJ (2002) Algorithmic aspects of k-tuple domination in graphs. Taiwan J Math 6:415–420
Liao CS, Chang GJ (2003) k-tuple domination in graphs. Inf Process Lett 87:45–50
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Dorbec, P., Hartnell, B. & Henning, M.A. Paired versus double domination in K 1,r -free graphs. J Comb Optim 27, 688–694 (2014). https://doi.org/10.1007/s10878-012-9547-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-012-9547-y