Upper distance-two domination

• Autorzy: Hedetniemi Jason T. , Hedetniemi Stephen T. , Lewis Thomas M.

Identyfikatory

DOI

10.7494/OpMath.2025.45.3.339

• Języki publikacji: EN

Abstrakty

EN

Let G = (V,E) be a graph with vertex set V and edge set E. A set S ⊂ V is a 2-packing in G if for any two vertices u, v ∈ S, the distance between them satisfies d(u, v) > 2. The upper 2-packing number P2(G) is the maximum cardinality of a 2-packing in G. A set S ⊂ V is a dominating set for G if every vertex in V − S is adjacent to at least one vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set in G. A set S ⊂ V is a distance-2 dominating set if for every vertex v ∈ V − S there exists a vertex u ∈ S such that d(u, v) ≤ 2. The upper distance-2 domination number Γ≤2(G) is the maximum cardinality of a minimal distance-2 dominating set in G. In this paper we establish two families of graphs G for which P2(G) = γ(G) = Γ≤2(G), which extend several well-known equalities of the form P2(G) = γ(G).

Słowa kluczowe

EN

2-packing; domination; distance-2 domination

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 3
• Strony: 339--350
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Hedetniemi Jason T.

• Florida Atlantic University, Harriet L. Wilkes Honors College, Boca Raton, FL, USA

autor

Hedetniemi Stephen T.

• Clemson University, Emeritus College, Clemson, SC, USA

autor

Lewis Thomas M.

• Furman University, Department of Mathematics, Greenville, SC, USA

• https://orcid.org/0000-0001-8366-2867

Bibliografia

• [1] B. Brešar, P. Dorbec, W. Goddard, B.L. Hartnell, M.A. Henning, S. Klavžar, D.F. Rall, Vizing’s conjecture: a survey and recent results, J. Graph Theory 69 (2012), no. 1, 46–76.
• [2] G.S. Domke, S. Hedetniemi, R. Laskar, R. Allan, Generalized packings and coverings of graphs, Congr. Numer. 62 (1988), 259–270, Seventeenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1987).
• [3] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Monographs and Textbooks in Pure and Applied Mathematics, 208, Marcel Dekker, Inc., New York, 1998.
• [4] M.A. Henning, O.R. Oellermann, H.C. Swart, Bounds on distance domination parameters, J. Combin. Inform. System Sci. 16 (1991), 11–18.
• [5] A. Meir, J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975), no. 1, 225–233.
• [6] R.R. Rubalcaba, A. Sneider, P.J. Slater, A survey on graphs which have equal domination and closed neighborhood packing numbers, AKCE Int. J. Graphs Comb. 3 (2006), no. 2, 93–114.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025)