On graph classes with constant domination-packing ratio
Marthe Bonamy, Mónika Csikós, Anna Gujgiczer, Yelena Yuditsky · 2025
Read On graph classes with constant domination-packing ratio by Marthe Bonamy, Mónika Csikós, Anna Gujgiczer, Yelena Yuditsky (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-2503-05562.txt.
Introduction
Marthe Bonamy, Mónika Csikós, Anna Gujgiczer, and Yelena Yuditsky bound a guard-to-gap share for graph kinds in a 2025 paper. The guard count is the least set whose reach caps all nodes of a graph in full. The gap count is the most nodes whose reach zones stay clear of each kin in the set.
Their share of the two counts stays in a fixed bound for some graph kinds at hand. A step proof wins the bound for lean graphs that shun dense cores in their form. Two more kinds, string-free and disc graphs, earn the same bound in the work.
Catalog record
| CREATOR | Marthe Bonamy, Mónika Csikós, Anna Gujgiczer, Yelena Yuditsky |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-05562
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On graph classes with constant domination-packing ratio Marthe Bonamy, Mónika Csikós, Anna Gujgiczer, Yelena Yuditsky Abstract The dominating number γ ( G ) \gamma(G) of a graph G G is the minimum size of a vertex set whose closed neighborhood covers all the vertices of the graph. The packing number ρ ( G ) \rho(G) of G G is the maximum size of a vertex set whose closed neighborhoods are pairwise disjoint. In this paper we study graph classes 𝒢 {\cal G} such that γ ( G ) / ρ ( G ) \gamma(G)/\rho(G) is bounded by a constant c 𝒢 c_{\cal G} for each G ∈ 𝒢 G\in{\cal G} . We propose an inductive proof technique to prove that if 𝒢 \cal G is the class of 2 2 -degenerate graphs, then there is such a constant bound c 𝒢 c_{\cal G} . We note that this is the first monotone, dense graph class that is shown to have constant ratio. We also show that the classes of AT-free and unit-disk graphs have bounded ratio. In addition, our technique gives improved bounds on c 𝒢 c_{\cal G} for planar graphs, graphs of bounded treewidth or bounded twin-width. Finally, we provide some new examples of graph classes where the ratio is unbounded. 1 Introduction The duality of packing and covering problems is well-known and their relation is widely studied in geometric setups. These two notions can naturally be translated to graphs using the notion of balls. Balls in graphs. Let G=(V,E) be a simple graph. The distance between two vertices v,u\in V , denoted \dist_{G}(u,v) , is the length of the shortest path between u and v in G . Let k\in\mathbb{N} and let a k -ball centered in v\in V(G) be the set of all vertices at distance at most k from v . For any v\in V let N_{G}[v] denote the 1 -ball centered in v , that is, the closed neighborhood of v in G and let N_{G}(v) denote N_{G}[v]\setminus\{v\} . The degree of v in G , denoted by \deg_{G}(v) is defined as |N_{G}(v)| . For any X\subseteq V let N_{G}[X] denote \bigcup_{v\in X}N_{G}[v] and let N_{G}(X) denote \bigcup_{v\in X}N_{G}(v) . In the notations above and in subsequent ones, we drop the subscript when G is clear from the context. Covering and packing. Covering a graph G with as few balls of radius 1 as possible is commonly known as finding a minimum dominating set of G . Formally, a dominating set in G is a collection of vertices such that the union of their closed neighborhoods contains all of V(G) . We denote the size of minimum dominating set in G by \gamma(G) . The dual of this problem is to maximize the number of disjoint balls of radius 1 that can be packed in a graph. Formally, a packing in G is a collection of vertices whose closed neighborhoods are pairwise disjoint. In other words, a set of vertices form a packing iff their pairwise distances are at least 3 . We let \rho(G) denote the size a maximum packing in G . A straightforward, general relation of \gamma(G) and \rho(G) is given by the following observation. For any graph G and any packing, a dominating set must have a non-empty intersection with each of the closed neighborhoods of the vertices of the packing, thus \gamma(G)\geqslant\rho(G) . In general those two parameters are not equal. Simple examples where \gamma(G)>\rho(G) include G=C_{4} or G=C_{5} . The problems of computing \gamma(G) and \rho(G) have natural formulations as integer programs. \displaystyle\text{minimize}\quad\sum_{v\in V(G)}x_{v} \displaystyle\text{maximize}\quad\sum_{v\in V(G)}y_{v} (1) \displaystyle\text{s.t.}\quad\sum_{u\in N[v]}x_{u}\geqslant 1,\mbox{ }\forall v\in V(G) \displaystyle\text{s.t.}\quad\sum_{u\in N[v]}y_{u}\leqslant 1,\mbox{ }\forall v\in V(G), \displaystyle\quad\quad x_{v}\in\{0,1\},\quad\forall v\in V(G) \displaystyle\quad\quad y_{v}\in\{0,1\},\quad\forall v\in V(G) The linear program relaxations of the above integer programs are dual, and their optimums are called fractional dominating and fractional packing numbers, respectively. One of the early papers studying the integrality gap of these problems was due to Lovász [ Lov75 ] , who showed that the ratio of integral and fractional dominating numbers is always at most \log(\Delta(G)) , where \Delta(G) denotes the maximum degree of G . In this paper, we study the following question. Question 1.1 . Given a graph class \mathcal{G} , is there a constant c_{\mathcal{G}} such that \frac{\gamma(G)}{\rho(G)}\leqslant c_{\mathcal{G}}\quad\text{ for each }\quad G\in\mathcal{G}~~? Importantly, a positive answer to this question immediately gives the bound c_{\mathcal{G}} on the integrality gap of both the dominating and the packing problem for any graph G\in\mathcal{G} . 1.1 Previous work There are graph classes for which the ratio \gamma/\rho is known to be equal to 1 , namely, trees [ MM75 , Theorem 7] , strongly chordal graphs [ Far84 , Corollary 3.4] , and dually chordal graphs [ BCD98 , Theorem 3.2] . The ratio is known to be at most 2 for cactus graphs [ LRR13 , Theorem 8] and connected biconvex graphs [ GG25 , Theorem 15] . Recently, it was also shown that for any bipartite cubic graph G , \gamma(G)\leqslant\frac{120}{49}\rho(G) holds [ GG25 , Theorem 5] and for any maximal outerplanar graph H , we have \gamma(H)\leqslant 3\rho(H) [ GG25 , Theorem 6] . 1.1.1 Low-degree graphs. A general upper bound of \gamma(G)\leqslant\Delta(G)\rho(G) follows by observing that the union of all neighbors of the vertices in a maximum packing is a dominating set in the graph. This observation was first stated by Henning et al. [ HLR11 ] who also showed that if \Delta(G)\leqslant 2 , then \gamma(G)\leqslant\rho(G)+1 with equality if and only if G=C_{n} and n\equiv 1,2\mod 3 . Furthermore, they proved that if G is claw-free graph with \Delta(G)\leqslant 3 , then \gamma(G)\leqslant 2\rho(G) and stated the following conjecture on general subcubic graphs. Conjecture 1.2 . [ HLR11 ] Let G be a connected graph with \Delta(G)\leqslant 3 , then \gamma(G)\leqslant 2\rho(G)+1 . The equality holds only for three well-defined graphs, one of which being the Petersen graph. 1.1.2 Graphs with no large complete bipartite minors. A graph H is a minor of a graph G if it can be obtained from G by deleting vertices and edges and by contracting edges. Böhme and Mohar [ BM03 ] studied the more general problem of packing and covering with balls of radius k in K_{q,r} -minor free graphs. Their results imply the following on the domination and packing numbers. Theorem 1.3 . [ BM03 , Corollary 1.2] If G does not contain a K_{q,r} -minor, then \gamma(G)<(4r+(q-1)(r+1))\rho(G)-3r+1 . Since graphs embedded in a surface of genus g cannot contain a K_{k,3} -minor for any 2g+3\leqslant k , the following bound holds. Corollary 1.4 . [ BM03 , Corollaries 1.3 and 1.4] Let G be a graph embedded in a surface of Euler genus g , then \gamma(G)\leqslant 4(2g+5)\rho(G)-9 . In particular, if G is a planar graph, then \gamma(G)\leqslant 20\rho(G)-9 . 1.1.3 Graphs with bounded weak coloring numbers. Theorem 1.3 was generalized in [ Dvo13 ] using the weak 1 -coloring and weak 2 -coloring numbers ( \mbox{wcol}_{1}(G) and \mbox{wcol}_{2}(G) ) of a graph G . Since in this paper we will not work directly with the notion of the weak coloring number, we spare its (lenghty) definition and only give