pith. sign in

arxiv: 2312.10485 · v2 · submitted 2023-12-16 · 💻 cs.DM · math.CO

Relation between broadcast domination and multipacking numbers on chordal and other hyperbolic graphs

Sandip Das , Florent Foucaud , Sk Samim Islam , Joydeep Mukherjee This is my paper

Pith reviewed 2026-05-24 05:14 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords chordal graphsbroadcast dominationmultipackinghyperbolic graphsdomination numberpacking numbergraph parameters
0
0 comments X

The pith

Connected chordal graphs satisfy γ_b(G) ≤ ⌈(3/2) mp(G)⌉, with constructions showing the ratio can reach 10/9.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes multiplicative bounds linking the broadcast domination number to the multipacking number in chordal graphs and δ-hyperbolic graphs. It proves that any connected chordal graph obeys an upper bound of ceiling of three-halves times the multipacking number, while also exhibiting infinite families where the ratio reaches 10/9 and the absolute difference grows arbitrarily large. A parallel inequality with an additive 2δ term is shown for δ-hyperbolic graphs, accompanied by a polynomial-time procedure to build a multipacking of guaranteed size. These relations matter because both parameters quantify how efficiently vertices can dominate or pack balls of increasing radii in a network. The results tie two covering-style measures together under structural restrictions that many real-world graphs satisfy.

Core claim

For any connected chordal graph G, γ_b(G) ≤ ⌈(3/2) mp(G)⌉. An infinite family of connected chordal graphs exists with γ_b(G)/mp(G) = 10/9 and mp(G) arbitrarily large, so that γ_b(G) − mp(G) is unbounded. For every δ-hyperbolic graph the inequality γ_b(G) ≤ ⌊(3/2) mp(G) + 2δ⌋ holds. In addition a polynomial-time algorithm produces a multipacking of size at least ⌈(2 mp(G) − 4δ)/3⌉ in any δ-hyperbolic graph.

What carries the argument

The direct comparison of the minimum dominating-broadcast cost γ_b(G) with the maximum multipacking cardinality mp(G), using chordal elimination orderings or negative-curvature bounds to control ball overlaps.

If this is right

  • In chordal graphs one parameter can be used to bound the other without computing both.
  • The ratio 10/9 is achievable and the absolute gap grows without limit even inside the chordal class.
  • Hyperbolic graphs admit the same style of bound with a correction linear in the hyperbolicity constant δ.
  • A guaranteed-size multipacking can be constructed in polynomial time for any δ-hyperbolic graph.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar ratio bounds may hold in other classes closed under certain elimination schemes, such as graphs of bounded treewidth.
  • The algorithmic construction for multipackings could be adapted to produce approximate broadcast solutions in hyperbolic networks.
  • Empirical checks on large random chordal graphs could reveal whether the 3/2 factor or the 10/9 ratio is typical in practice.

Load-bearing premise

The structural restrictions of chordal graphs and bounded-hyperbolicity graphs suffice to derive the stated multiplicative and additive relations between broadcast cost and multipacking size.

What would settle it

A single connected chordal graph G for which γ_b(G) > ⌈(3/2) mp(G)⌉ would refute the main chordal-graph inequality.

Figures

Figures reproduced from arXiv: 2312.10485 by Florent Foucaud, Joydeep Mukherjee, Sandip Das, Sk Samim Islam.

Figure 1
Figure 1. Figure 1: Inclusion diagram for graph classes mentioned in this paper (and related ones). If a class [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: S3 is a connected chordal graph with γb(S3) = 2 and mp(S3) = 1 F m1 m2 3 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: F is a connected chordal graph with γb(F) = 3 and mp(F) = 2 m1 m2 m4 m3 H 2 2 2 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: H is a connected chordal graph with γb(H) = 6 and mp(H) = 4 Here we have some examples of graphs that achieve the equality of the bound in Proposition 1. Example 1. The connected chordal graph S3 ( [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: G1 is a connected chordal graph with γb(G1) = 5 and mp(G1) = 5. M1 = {mi : 1 ≤ i ≤ 5} is a multipacking of size 5. Consider the graph G1 as in [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Graph G2 with γb(G2) = 10 and mp(G2) = 9. M = {mi : 1 ≤ i ≤ 9} is a multipacking of size 9. Proof. If d(u, v) = 1, then u, v ∈ N1[v]∩M, then M cannot be a multipacking. So, d(u, v) ̸= 1. If d(u, v) = 2, then there exists a common neighbour w of u and v. So, u, v ∈ N1[w]∩M, then M cannot be a multipacking. So, d(u, v) ̸= 2. Therefore, d(u, v) > 2. Lemma 2. mp(G2k) ≥ 9k, for each positive integer k. Proof. C… view at source ↗
Figure 7
Figure 7. Figure 7: Graph Gk We establish this lemma by using contradiction on |M|. In the first step, we prove that if |M1| = 5, then the particular vertex b1,21 ∈ M1. Using this, we can show that |M2| ≤ 4. In this way we show that |M| ≤ 9. For the purpose of contradiction, we assume that |M| = 10. So, |M1| + |M2| = 10, and also |M1| ≤ 5, |M2| ≤ 5. Therefore, |M1| = |M2| = 5. Claim 4.1. If |M1| = 5, then b1,21 ∈ M1. Proof of… view at source ↗
Figure 8
Figure 8. Figure 8: Graph Gk Lemma 7. If k is a positive integer, then mpf (Gk) = γb(Gk) = 5k. Proof. Define a broadcast f on Gk as f(bi,j ) =    2 if 1 ≤ i ≤ k and j = 6, 17 1 if 1 ≤ i ≤ k and j = 12 0 otherwise . Here f is an efficient dominating broadcast and P v∈V (Gk) f(v) = 5k. So, γb(Gk) ≤ 5k, ∀k ∈ N. So, by the strong duality theorem and Lemma 6, 5k ≤ mpf (Gk) = γb,f (Gk) ≤ γb(Gk) ≤ 5k. Therefore, mpf (Gk) = γb(G… view at source ↗
read the original abstract

For a graph $ G = (V, E) $ with a vertex set $ V $ and an edge set $ E $, a function $ f : V \rightarrow \{0, 1, 2, . . . , diam(G)\} $ is called a \emph{broadcast} on $ G $. For each vertex $ u \in V $, if there exists a vertex $ v $ in $ G $ (possibly, $ u = v $) such that $ f (v) > 0 $ and $ d(u, v) \leq f (v) $, then $ f $ is called a dominating broadcast on $ G $. The cost of the dominating broadcast $f$ is the quantity $ \sum_{v\in V}f(v) $. The minimum cost of a dominating broadcast is the broadcast domination number of $G$, denoted by $ \gamma_{b}(G) $. A multipacking is a set $ S \subseteq V $ in a graph $ G = (V, E) $ such that for every vertex $ v \in V $ and for every integer $ r \geq 1 $, the ball of radius $ r $ around $ v $ contains at most $ r $ vertices of $ S $, that is, there are at most $ r $ vertices in $ S $ at a distance at most $ r $ from $ v $ in $ G $. The multipacking number of $ G $ is the maximum cardinality of a multipacking of $ G $ and is denoted by $ mp(G) $. We show that, for any connected chordal graph $G$, $\gamma_{b}(G)\leq \big\lceil{\frac{3}{2} mp(G)\big\rceil}$. We also show that $\gamma_b(G)-mp(G)$ can be arbitrarily large for connected chordal graphs by constructing an infinite family of connected chordal graphs such that the ratio $\gamma_b(G)/mp(G)=10/9$, with $mp(G)$ arbitrarily large. Moreover, we show that $\gamma_{b}(G)\leq \big\lfloor{\frac{3}{2} mp(G)+2\delta\big\rfloor} $ holds for all $\delta$-hyperbolic graphs. In addition, we provide a polynomial-time algorithm to construct a multipacking of a $\delta$-hyperbolic graph $G$ of size at least $ \big\lceil{\frac{2mp(G)-4\delta}{3} \big\rceil} $.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper establishes relations between the broadcast domination number γ_b(G) and the multipacking number mp(G). For connected chordal graphs, it proves γ_b(G) ≤ ⌈(3/2) mp(G)⌉. It constructs an infinite family of connected chordal graphs where γ_b(G)/mp(G) = 10/9 with mp(G) arbitrarily large. For δ-hyperbolic graphs, it proves γ_b(G) ≤ ⌊(3/2) mp(G) + 2δ⌋ and gives a polynomial-time algorithm to construct a multipacking of size at least ⌈(2mp(G) - 4δ)/3⌉.

Significance. If the results hold, they provide meaningful bounds relating domination and packing in graphs with special structure. The chordal graph result and the explicit construction showing a ratio of 10/9 are particularly useful for understanding the parameters. The extension to hyperbolic graphs and the algorithmic contribution add value. The paper ships explicit constructions and an algorithm, which are strengths.

major comments (2)
  1. Section 3, Theorem 3.1: the proof of γ_b(G) ≤ ⌈(3/2) mp(G)⌉ for chordal graphs relies on induction along a perfect elimination ordering, but the extension step from a multipacking in G-v to one in G does not explicitly verify that the r-ball condition is preserved for all r when adding back the simplicial vertex v.
  2. Section 4: the infinite family construction achieving ratio exactly 10/9 is load-bearing for the claim that γ_b - mp can be arbitrarily large; the general-member calculation of both mp(G) and γ_b(G) must be supplied in full to confirm the ratio is not smaller than 10/9.
minor comments (2)
  1. Abstract: the floor/ceiling expressions in the three displayed bounds use inconsistent spacing around the symbols; standardize the notation.
  2. The running-time analysis of the polynomial-time multipacking algorithm in the hyperbolic case should cite the specific data structures used for distance queries.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the major comments point by point below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: Section 3, Theorem 3.1: the proof of γ_b(G) ≤ ⌈(3/2) mp(G)⌉ for chordal graphs relies on induction along a perfect elimination ordering, but the extension step from a multipacking in G-v to one in G does not explicitly verify that the r-ball condition is preserved for all r when adding back the simplicial vertex v.

    Authors: We thank the referee for identifying this point. The chordal property and the fact that v is simplicial ensure that any ball intersecting the neighborhood of v behaves like a clique, so the r-ball counts cannot increase beyond the bound when v is added (either the multipacking set remains unchanged or v is not added if it would violate a local condition). However, we acknowledge that an explicit case analysis for arbitrary r was not written out. In the revision we will add a dedicated paragraph in the proof of Theorem 3.1 that verifies the r-ball condition for every r ≥ 1 after re-inserting v. revision: yes

  2. Referee: Section 4: the infinite family construction achieving ratio exactly 10/9 is load-bearing for the claim that γ_b - mp can be arbitrarily large; the general-member calculation of both mp(G) and γ_b(G) must be supplied in full to confirm the ratio is not smaller than 10/9.

    Authors: We agree that the general-member verification is necessary for completeness. The construction is defined by a recursive attachment of 9-vertex blocks to a path-like backbone; for the k-th member we have mp(G_k) = 9k and γ_b(G_k) = 10k. In the revised Section 4 we will include the full inductive argument establishing both equalities for arbitrary k, together with the explicit multipacking and broadcast functions that achieve these values. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper states direct inequalities γ_b(G) ≤ ⌈(3/2) mp(G)⌉ for chordal graphs and γ_b(G) ≤ ⌊(3/2) mp(G) + 2δ⌋ for δ-hyperbolic graphs, plus an explicit infinite family construction achieving ratio 10/9. These follow from standard structural properties (perfect elimination orderings for chordal graphs; thin-triangle property for hyperbolic graphs) that are externally known and not defined in terms of the target parameters. No fitted inputs are relabeled as predictions, no self-citations are load-bearing for the central claims, and no ansatz or renaming reduces the result to its inputs by construction. The derivation chain is self-contained against the graph-class definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard axioms of undirected graph theory and the definitions of chordal and δ-hyperbolic graphs; no free parameters, invented entities, or ad-hoc constants are introduced.

axioms (2)
  • domain assumption Graphs are finite, undirected, and connected.
    Invoked in all statements of the results.
  • domain assumption Chordal graphs admit perfect elimination orderings and δ-hyperbolic graphs satisfy the δ-hyperbolicity inequality on distances.
    These are the structural properties used to derive the bounds.

pith-pipeline@v0.9.0 · 6032 in / 1392 out tokens · 42991 ms · 2026-05-24T05:14:05.112616+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · 1 internal anchor

  1. [1]

    S. Das, F. Foucaud, S. S. Islam, J. Mukherjee, Relation between broadcast domination and multipack- ing numbers on chordal graphs, in: A. Bagchi, R. Muthu (Eds.), Algorithms and Discrete Applied Mathematics - 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9-11, 2023, Proceedings, Vol. 13947 of Lecture Notes in Computer Science, Sp...

    work page 2023

  2. [2]

    Cornu´ ejols, Combinatorial optimization: Packing and covering, SIAM, 2001

    G. Cornu´ ejols, Combinatorial optimization: Packing and covering, SIAM, 2001

    work page 2001

  3. [3]

    J. E. Dunbar, D. J. Erwin, T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, Broadcasts in graphs, Discrete Applied Mathematics 154 (1) (2006) 59–75

    work page 2006

  4. [4]

    D. J. Erwin, Dominating broadcasts in graphs, Bull. Inst. Combin. Appl 42 (89) (2004) 105. 12

    work page 2004

  5. [5]

    D. J. Erwin, Cost domination in graphs, Western Michigan University, 2001

    work page 2001

  6. [6]

    L. E. Teshima, Broadcasts and multipackings in graphs, Master’s thesis, University of Victoria (2012)

    work page 2012

  7. [7]

    Beaudou, R

    L. Beaudou, R. C. Brewster, On the multipacking number of grid graphs, Discrete Mathematics & Theoretical Computer Science 21 (Graph Theory) (2019)

    work page 2019

  8. [8]

    A. Meir, J. Moon, Relations between packing and covering numbers of a tree, Pacific Journal of Math- ematics 61 (1) (1975) 225–233

    work page 1975

  9. [9]

    Heggernes, D

    P. Heggernes, D. Lokshtanov, Optimal broadcast domination in polynomial time, Discrete Mathematics 306 (24) (2006) 3267–3280

    work page 2006

  10. [10]

    R. C. Brewster, G. MacGillivray, F. Yang, Broadcast domination and multipacking in strongly chordal graphs, Discrete Applied Mathematics 261 (2019) 108–118

    work page 2019

  11. [11]

    Foucaud, B

    F. Foucaud, B. Gras, A. Perez, F. Sikora, On the complexity of broadcast domination and multipacking in digraphs, Algorithmica 83 (9) (2021) 2651–2677

    work page 2021

  12. [12]

    R. C. Brewster, C. M. Mynhardt, L. E. Teshima, New bounds for the broadcast domination number of a graph, Central European Journal of Mathematics 11 (2013) 1334–1343

    work page 2013

  13. [13]

    Beaudou, R

    L. Beaudou, R. C. Brewster, F. Foucaud, Broadcast domination and multipacking: bounds and the integrality gap, The Australasian Journal of Combinatorics 74 (1) (2019) 86–97

    work page 2019

  14. [14]

    B. L. Hartnell, C. M. Mynhardt, On the difference between broadcast and multipacking numbers of graphs, Utilitas Mathematica 94 (2014) 19–29

    work page 2014

  15. [15]

    Gromov, Hyperbolic groups, in: Essays in group theory, Springer, 1987, pp

    M. Gromov, Hyperbolic groups, in: Essays in group theory, Springer, 1987, pp. 75–263

    work page 1987

  16. [16]

    Brinkmann, J

    G. Brinkmann, J. H. Koolen, V. Moulton, On the hyperbolicity of chordal graphs, Annals of Combina- torics 5 (1) (2001) 61–69

    work page 2001

  17. [17]

    D. G. Corneil, B. Dalton, M. Habib, Ldfs-based certifying algorithm for the minimum path cover problem on cocomparability graphs, SIAM Journal on Computing 42 (3) (2013) 792–807

    work page 2013

  18. [18]

    D. G. Corneil, S. Olariu, L. Stewart, Asteroidal triple-free graphs, SIAM Journal on Discrete Mathe- matics 10 (3) (1997) 399–430

    work page 1997

  19. [19]

    M. C. Golumbic, Algorithmic graph theory and perfect graphs, Elsevier, 2004

    work page 2004

  20. [20]

    Chepoi, F

    V. Chepoi, F. Dragan, B. Estellon, M. Habib, Y. Vax` es, Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs, in: Proceedings of the twenty-fourth annual symposium on Computational geometry, 2008, pp. 59–68

    work page 2008

  21. [21]

    J. M. Keil, J. S. Mitchell, D. Pradhan, M. Vatshelle, An algorithm for the maximum weight independent set problem on outerstring graphs, Computational Geometry 60 (2017) 19–25

    work page 2017

  22. [22]

    Shavitt, T

    Y. Shavitt, T. Tankel, On the curvature of the internet and its usage for overlay construction and distance estimation, in: IEEE INFOCOM 2004, Vol. 1, IEEE, 2004, p. 384

    work page 2004

  23. [23]

    J. A. Walter, H. Ritter, On interactive visualization of high-dimensional data using the hyperbolic plane, in: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, 2002, pp. 123–132

    work page 2002

  24. [24]

    Brewster, L

    R. Brewster, L. Duchesne, Broadcast domination and fractional multipackings, manuscript (2013)

    work page 2013

  25. [25]

    Y. Wu, C. Zhang, Hyperbolicity and chordality of a graph, The Electronic Journal of Combinatorics 18 (1) (2011) P43. 13

    work page 2011

  26. [26]

    Dourisboure, C

    Y. Dourisboure, C. Gavoille, Tree-decompositions with bags of small diameter, Discrete Mathematics 307 (16) (2007) 2008–2029

    work page 2007

  27. [27]

    Laskar, D

    R. Laskar, D. Shier, On powers and centers of chordal graphs, Discrete Applied Mathematics 6 (2) (1983) 139–147

    work page 1983

  28. [28]

    L. E. Teshima, Multipackings in graphs, arXiv preprint arXiv:1409.8057 (2014). 14

    work page internal anchor Pith review Pith/arXiv arXiv 2014