2025/07/24 by Csilla Bujtás, Bujtás, Csilla, Vesna Iršič Chenoweth +5 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2507.18272
openalex publication_date 2025/07/24 · openalex created_date 2025/10/16 · openalex updated_date 2026/07/28
A set of vertices X⊆ V(G) is a d-distance dominating set if for every u∈ V(G)∖ X there exists x∈ X such that d(u,x) ≤ d, and X is a p-packing if d(u,v) ≥ p+1 for every different u,v∈ X. The d-distance p-packing domination number γdp(G) of G is the minimum size of a set of vertices of G which is both a d-distance dominating set and a p-packing. It is proved that for every two fixed integers d and p with 2 ≤ d and 0 ≤ p ≤ 2d-1, the decision problem whether γdp(G) ≤ k holds is NP-complete for bipartite planar graphs. A necessary and sufficient condition for the existence of a d-distance p-packing dominating set in Cn is obtained and γdp(Cn) determined for every d, p, and n. For a tree T on n vertices with ℓ leaves and s support vertices it is proved that (i) γ20(T) ≥ (n-ℓ-s+4)/(5), (ii) \lceil (n-ℓ-s+4)/(5) \rceil ≤ γ22(T) ≤ \lfloor (n+3s-1)/(5) \rfloor, and if d ≥ 2, then (iii) γd2(T) ≤ (n-2√(n)+d+1)/(d). Inequality (i) improves an earlier bound due to Meierling and Volkmann, and independently Raczek, Lemańska, and Cyman, while (iii) extends an earlier result for γ22(T) due to Henning. Sharpness of the bounds are discussed and established in most cases. It is also proved that every connected graph G contains a spanning tree T such that γ22(T) ≤ γ22(G).