All graphs with paired-domination number two less than their order

• Autorzy: Ulatowski W.
• Języki publikacji: EN

Abstrakty

EN

Let G = (V,E) be a graph with no isolated vertices. A set S ⊆ V is a paired-dominating set of G if every vertex not in S is adjacent with some vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination number Υρ (G) of G is defined to be the minimum cardinality of a paired-dominating set of G. Let G be a graph of order n. In [Paired-domination in graphs, Networks 32 (1998), 199–206] Haynes and Slater described graphs G with Υρ (G) = n and also graphs with Υρ (G) = n − 1. In this paper we show all graphs for which Υρ (G) = n − 2.

Słowa kluczowe

EN

paired-domination; paired-domination number

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2013
• Tom: Vol. 33, no. 4
• Strony: 763--783
• Opis fizyczny: Bibliogr. 5 poz., rys.

Twórcy

autor

Ulatowski W.

• Gdansk University of Technology Department of Technical Physics and Applied Mathematics Narutowicza 11/12, 80–952 Gdansk, Poland

Bibliografia

• [1] M. Chellali, T.W. Haynes, Trees with unique minimum paired-dominating set, Ars Combin. 73 (2004), 3–12.
• [2] S. Fitzpatrick, B. Hartnell, Paired-domination, Discuss. Math. Graph Theory 18 (1998), 63–72.
• [3] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
• [4] T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199–206.
• [5] M.A. Henning, Graphs with large paired-domination number, J. Comb. Optim. 13 (2007), 61–78.