Revisiting d d -distance (independent) domination in trees and in bipartite graphs
Csilla Bujtás, Vesna Iršič Chenoweth, Sandi Klavžar, Gang Zhang · 2025
Read Revisiting d d -distance (independent) domination in trees and in bipartite graphs by Csilla Bujtás, Vesna Iršič Chenoweth, Sandi Klavžar, Gang Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-12804.txt.
Introduction
Bujtás, Iršič Chenoweth, Klavžar, and Zhang wrote in twenty twenty-five about domination numbers in trees and bipartite graphs. A dominating set is a set of vertices within a set distance of every vertex. Packing conditions add spacing requirements between chosen vertices. A nineteen ninety-four conjecture bounded this number for trees of a given size. It was proven only for small distance values before. The authors prove the bound for all bipartite graphs and every distance.
They also characterize the trees where the bound is met exactly. Sharper bounds use the number of leaves a tree has. One extends a classic nineteen ninety-two theorem to all distances. Equality cases are characterized for those bounds too. Consequences for the plain distance domination number follow. The paper settles a three-decade-old conjecture in graph theory.
Catalog record
| CREATOR | Csilla Bujtás, Vesna Iršič Chenoweth, Sandi Klavžar, Gang Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-12804
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Revisiting d d -distance (independent) domination in trees and in bipartite graphs Csilla Bujtás, Vesna Iršič Chenoweth, Sandi Klavžar, Gang Zhang Abstract The d d -distance p p -packing domination number γ d p ( G ) \gamma_{d}^{p}(G) of G G is the minimum size of a set of vertices of G G which is both a d d -distance dominating set and a p p -packing. In 1994, Beineke and Henning conjectured that if d ≥ 1 d\geq 1 and T T is a tree of order n ≥ d + 1 n\geq d+1 , then γ d 1 ( T ) ≤ n d + 1 \gamma_{d}^{1}(T)\leq\frac{n}{d+1} . They supported the conjecture by proving it for d ∈ { 1 , 2 , 3 } d\in\{1,2,3\} . In this paper, it is proved that γ d 1 ( G ) ≤ n d + 1 \gamma_{d}^{1}(G)\leq\frac{n}{d+1} holds for any bipartite graph G G of order n ≥ d + 1 n\geq d+1 , and any d ≥ 1 d\geq 1 . Trees T T for which γ d 1 ( T ) = n d + 1 \gamma_{d}^{1}(T)=\frac{n}{d+1} holds are characterized. It is also proved that if T T has ℓ \ell leaves, then γ d 1 ( T ) ≤ n − ℓ d \gamma_{d}^{1}(T)\leq\frac{n-\ell}{d} (provided that n − ℓ ≥ d n-\ell\geq d ), and γ d 1 ( T ) ≤ n + ℓ d + 2 \gamma_{d}^{1}(T)\leq\frac{n+\ell}{d+2} (provided that n ≥ d n\geq d ). The latter result extends Favaron’s theorem from 1992 asserting that γ 1 1 ( T ) ≤ n + ℓ 3 \gamma_{1}^{1}(T)\leq\frac{n+\ell}{3} . In both cases, trees that attain the equality are characterized and relevant conclusions for the d d -distance domination number of trees derived. a Faculty of Mathematics and Physics, University of Ljubljana, Slovenia b Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia c Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia d School of Mathematical Sciences, Xiamen University, China Keywords: d -distance dominating set; p -packing set; tree; bipartite graph AMS Subj. Class. (2020) : 05C69, 05C05 1 Introduction Let G=(V(G),E(G)) be a graph, S\subseteq V(G) , let d and p be nonnegative integers, and let d(\,\cdot\,,\,\cdot\,) denote the standard shortest-path distance. Then S is a d -distance dominating set of G if for every vertex u\in V(G)\setminus S there exists a vertex w\in S such that d(u,w)\leq d , and S is a p -packing of G if d(w,w^{\prime})\geq p+1 for every two different vertices w,w^{\prime}\in S . The d -distance p -packing domination number \gamma_{d}^{p}(G) of G is the minimum size of a set S which is at the same time d -distance dominating set and p -packing. (If for some parameters d and p such a set does not exist, set \gamma_{d}^{p}(G)=\infty .) The d -distance p -packing domination number was introduced by Beineke and Henning [ 1 ] under the name (p,d) -domination number and with the notation i_{p,d}(G) . With the intention of placing it within the trends of contemporary graph domination theory, the notation \gamma_{d}^{p}(G) was recently proposed in [ 2 ] and we follow it here. In [ 2 ] it is proved that for every two fixed integers d and p with 2\leq d and 0\leq p\leq 2d-1 , the decision problem whether \gamma_{d}^{p}(G)\leq k holds is NP-complete for bipartite planar graphs. Several bounds on \gamma_{d}^{p}(T) , where T is a tree on n vertices with \ell leaves and s support vertices are also proved, including \gamma_{2}^{0}(T)\geq\frac{n-\ell-s+4}{5} and \gamma_{d}^{2}(T)\leq\frac{n-2\sqrt{n}+d+1}{d} , d\geq 2 . These results improve or extend earlier results from the literature. In this paper, our focus is on the invariants \gamma_{d}^{0} and \gamma_{d}^{1} . For the first one we will simplify the notation to \gamma_{d} because it has been investigated under the name of d -distance domination number of G with the notation \gamma_{d}(G) , see the survey [ 8 ] . We also refer to [ 3 ] for algorithmic aspects. For the total version of this concept see [ 4 ] . The second invariant \gamma_{d}^{1} deals with d -distance dominating sets which are 1 -packings. Note that a set of vertices is a 1 -packing if and only if it is an independent set, hence in this case we will say that \gamma_{d}^{1}(G) is the d -distance independent domination number of G , cf. [ 5 , 7 , 8 ] . Meierling and Volkmann [ 10 ] , and independently Raczek, Lemańska, and Cyman [ 12 ] , proved that if d\geq 1 , and T is a tree on n vertices and with \ell leaves, then \gamma_{d}(T)\geq\frac{n-d\ell+2d}{2d+1} . On the other hand, Meir and Moon [ 11 ] proved that if d\geq 1 and T is a tree of order n\geq d+1 , then \gamma_{d}(T)\leq\frac{n}{d+1} . About twenty years later, in 1991, Topp and Volkmann [ 13 ] gave a complete characterization of the graphs G with \gamma_{d}(G)=\frac{n}{d+1} . In 1994, Beineke and Henning [ 1 ] proved that if d\in\{1,2,3\} and T is a tree of order n\geq d+1 , then \gamma_{d}^{1}(T)\leq\frac{n}{d+1} . Moreover, they closed their paper with the following: Conjecture 1.1 . [ 1 ] If d\geq 1 and T is a tree of order n\geq d+1 , then \gamma_{d}^{1}(T)\leq\frac{n}{d+1} . We point out here that in the book’s chapter [ 8 ] , Conjecture 1.1 is stated as [ 8 , Theorem 71] with the explanation that the above-mentioned bound on \gamma_{d}(T) due to Meir and Moon [ 11 ] is proved in such a way, that the d -distance dominating set is also independent. Anyhow, in the next section we prove that the bound holds for all bipartite graphs. In Section 3 we then characterize trees T of order n for which \gamma_{d}^{1}(T)=\frac{n}{d+1} holds. In Section 4 , we prove that if T has \ell leaves, then \gamma_{d}^{1}(T)\leq\frac{n-\ell}{d} (provided that n-\ell\geq d ), and \gamma_{d}^{1}(T)\leq\frac{n+\ell}{d+2} (provided that n\geq d ). In both cases, the trees that attain the equality are characterized. Using the fact that \gamma_{d}(T)\leq\gamma_{d}^{1}(T) , we also derive analogous bounds for \gamma_{d}(T) and characterize trees attaining those bounds. In particular, if T is a tree with \ell leaves and of order n\geq d+\ell , then \gamma_{d}(T)\leq\gamma_{d}^{1}(T)\leq\begin{cases}\frac{n-\ell}{d},&\text{if\penalty\ }n<(d+1)\ell,\\ \frac{n}{d+1},&\text{if\penalty\ }n=(d+1)\ell,\\ \frac{n+\ell}{d+2},&\text{if\penalty\ }n>(d+1)\ell,\\ \end{cases} and the upper bounds are best possible. We conclude the paper with a conjecture. In the rest of the introduction additional definitions necessary for understanding the rest of the paper are given. For a positive integer n we will use the convention [n]=\{1,\dots,n\} . Let G be a graph. The degree of u\in V(G) is denoted by \deg_{G}(u) or \deg(u) for short. Further, \diam(G) is the diameter of G and L(G) is the set of its leaves, that is, vertices of degree 1 . We call a d -distance p -packing dominating set of G of size \gamma_{d}^{p}(G) a \gamma_{d}^{p}(G) -set . When G is clear from the context, we may shorten it to \gamma_{d}^{p} -set . A double star D_{r,s} is a tree with exactly two vertices that are not leaves, with one adjacent to r\geq 1 leaves and the other to