The paired-domination and the upper paired-domination numbers of graphs

• Autorzy: Ulatowski W.

Identyfikatory

DOI

http://dx.doi.Org/10.7494/OpMath.2015.35.l.127

• Języki publikacji: EN

Abstrakty

EN

In this paper we continue the study of paired-domination in graphs. A paired-dominating set, abbreviated PDS, of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γP(G), is the minimum cardinality of a PDS of G. The upper paired-domination number of G, denoted by ΓP(G), is the maximum cardinality of a minimal PDS of G. Let G be a connected graph of order n ≥ 3. Haynes and Slater in [Paired-domination in graphs, Networks 32 (1998), 199-206], showed that γ P(G) ≤ n— 1 and they determine the extremal graphs G achieving this bound. In this paper we obtain analo­gous results for ΓP(G). Dorbec, Henning and McCoy in [Upper total domination versus upper paired-domination, Questiones Mathematicae 30 (2007), 1-12] determine Γp(Pn), instead in this paper we determine Γp(Cn). Moreover, we describe some families of graphs G for which the equality γP(G) = ΓP(G) holds.

Słowa kluczowe

EN

paired-domination; paired-domination number; upper paired-domination number

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2015
• Tom: Vol. 35, no. 1
• Strony: 127--135
• Opis fizyczny: Bibliogr.10 poz.

Twórcy

autor

Ulatowski W.

• Gdansk University ol Technology Faculty ol Physics and Mathematics Narutowicza 11/12, 80-233 Gdańsk, Poland

Bibliografia

• [1] M. Chellali, T.W. Haynes, Trees with unique minimum paired-dominating sets, Ars Combin. 73 (2004), 3-12.
• [2] P. Dorbec, M.A. Henning, J. McCoy, Upper total domination versus upper paired--domination, Quest. Math. 30 (2007), 1-12.
• [3] P. Dorbec, S. Gravier, M.A. Henning, Paired- domination in generalized claw-free graphs, J. Comb. Optim. 14 (2007), 1-7.
• [4] O. Favaron, M.A. Henning, Paired-domination in claw-free cubic graphs, Graphs Comb. 20 (2004), 447-456.
• [5] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of domination in graphs, Marcel Dekker, New York, 1998.
• [6] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in graphs: advanced topics, Marcel Dekker, New York, 1998.
• [7] T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199-209.
• [8] M.A. Henning, Graphs with large paired-domination number, J. Comb. Optim. 13 (2007), 61-78.
• [9] J. Raczek, Lower bound on the paired-domination number of a tree, Australas. J. Comb. 34 (2006), 343-347.
• [10] W. Ulatowski, All graphs with paired-domination number two less than their order, Opuscula Math. 33 (2013) 4, 763-783.