Paired-domination in \(P_{5}\)-free graphs. (English) Zbl 1193.05123

Summary: A set \(S\) of vertices in a graph \(G\) is a paired-dominating set of \(G\) if every vertex of \(G\) is adjacent to some vertex in \(S\) and if the subgraph induced by \(S\) contains a perfect matching. The paired-domination number of \(G\), denoted by \(\gamma_{\text{pr}}(G)\), is the minimum cardinality of a paired-dominating set of \(G\). In [P. Dorbec, S. Gravier, and M.A. Henning, “Paired-domination in generalized claw-free graphs”, J. Comb. Optim. 14, No. 1, 1–7 (2007; Zbl 1180.05088)], the authors gave tight bounds for paired-dominating sets of generalized claw-free graphs. Yet, the critical cases are not claws but subdivided stars. We here give a bound for graphs containing no induced \(P_{5}\), which seems to be the critical case.


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI


[1] Dorbec, P., Gravier, S., Henning, M.A.: Paired-domination in generalized claw-free graphs. J. Combin. Optim. 14(1), 1–7 (2007) · Zbl 1125.05072
[2] Favaron, O., Henning, M.A.: Paired-domination in claw-free cubic graphs. Graphs Combin. 20, 447–456 (2004) · Zbl 1054.05074
[3] Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. (Marcel Dekker, New York, 1998) · Zbl 0890.05002
[4] Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: (eds), Domination in Graphs: Advanced Topics. (Marcel Dekker, New York, 1998) · Zbl 0883.00011
[5] Haynes, T.W., Slater, P.J.: Paired-domination in graphs. Networks 32, 199–206 (1998) · Zbl 0997.05074
[6] Haynes, T.W., Slater, P.J.: Paired-domination and the paired-domatic number. Congr. Numer. 109, 65–72 (1995) · Zbl 0904.05052
[7] Seinsche, D.: On a property of the class of n-colorable graphs. J. Combin. Theory Ser. B 16, 191–193 (1974) · Zbl 0269.05103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.