pith. sign in

arxiv: 2606.18172 · v1 · pith:CMTOYIBOnew · submitted 2026-06-16 · 🧮 math.CO

On the Relationships between Domination, Isolation, and Packing

Geoffrey Boyer , Wayne Goddard , Michael A. Henning This is my paper

Pith reviewed 2026-06-26 23:38 UTC · model grok-4.3

classification 🧮 math.CO
keywords domination numberpacking numberisolation numbertreesinterval graphspermutation graphsasteroidal-triple-free graphs
0
0 comments X

The pith

While the ratio of domination number to lower packing number can grow without bound in trees, the isolation number is always less than twice the distance-2 domination number in every tree.

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

The paper studies the relationships among five domination-related parameters on graphs: the ordinary domination number γ, the distance-2 domination number γ₂, the packing number ρ, the lower packing number ρ_L, and the isolation number ι. It establishes that one ratio is unbounded on trees while another ratio is bounded by 2, and it supplies explicit upper bounds on the domination-to-lower-packing ratio for three additional hereditary graph classes. The work further proves that every tree admits a vertex set that is simultaneously isolating and a packing, and it gives a characterization of the trees in which the packing number equals the lower packing number.

Core claim

The authors establish that γ/ρ_L is unbounded in trees while ι/γ₂ is less than 2 for all trees. They prove that γ/ρ_L is at most 3 in interval graphs, at most 4 in permutation graphs, and at most 5 in asteroidal-triple-free graphs. They also show that every tree has a set of vertices that is both isolating and a packing, and they characterize the trees for which ρ equals ρ_L.

What carries the argument

The ratios γ/ρ_L and ι/γ₂ together with the existence of an isolating packing, applied to the structural properties of trees and the three stated graph classes.

If this is right

  • The ratio γ/ρ_L can be made arbitrarily large by selecting suitable trees.
  • The isolation number of any tree satisfies ι < 2 γ₂.
  • Interval graphs obey the inequality γ ≤ 3 ρ_L.
  • Permutation graphs obey γ ≤ 4 ρ_L and asteroidal-triple-free graphs obey γ ≤ 5 ρ_L.
  • Every tree contains a vertex set that is simultaneously an isolating set and a packing set.

Where Pith is reading between the lines

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

  • The separation between the unbounded γ/ρ_L behavior and the bounded ι/γ₂ behavior on trees may indicate that isolation captures a stricter local condition than lower packing.
  • The guaranteed existence of an isolating packing in trees could be used to construct small dominating sets by first selecting such a mixed set.
  • The characterization of trees with ρ = ρ_L may allow algorithmic recognition of trees whose minimum packings are also minimum lower packings.
  • The ratio bounds on interval, permutation, and AT-free graphs suggest that forbidding asteroidal triples controls the gap between domination and lower packing.

Load-bearing premise

The standard definitions of the five parameters are used together with the usual hereditary properties of trees, interval graphs, permutation graphs, and asteroidal-triple-free graphs.

What would settle it

A single tree in which the isolation number is at least twice the distance-2 domination number, or an interval graph whose domination number exceeds three times its lower packing number.

Figures

Figures reproduced from arXiv: 2606.18172 by Geoffrey Boyer, Michael A. Henning, Wayne Goddard.

Figure 1
Figure 1. Figure 1: A tree T˜ with packing number more than isolation number. While we observed earlier that a packing isolating set (of a graph with mini￾mum degree at least 1) contains at most half the vertices, trees do not necessarily 5 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Two graphs with no packing isolating set. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The tree P ∗ 4 with ι = 7 and γ2 = ρL = 4. Lemma 6 For any graph H with n vertices and m edges it holds that ρL(H∗ ) = n and ι(H∗ ) = n + m. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A MOP with ι ≫ ρL 4.2 Well-Packed Trees One question of interest with any collection of sets in a graph is when do all the sets have the same size. Thus, for example, in well-covered graphs all maximal independent sets have the same size and in well-dominated graphs all minimal dominating sets have the same size. Recently, Boutrig, Chellali, and Meddah [4] determined the trees where every minimal independe… view at source ↗
Figure 5
Figure 5. Figure 5: A tree in P We note that the well-ve-dominated / well-ve-covered trees are the trees in P where every vertex of X has at most one non-leaf neighbor. Theorem 7 For n ≥ 3, a tree T is well-packed if and only if T is in P. Proof. (1) We need to show that every tree in P is well-packed. Consider a tree T ∈ P. Every packing of T contains at most one vertex from each constituent star. Furthermore, the leaf verte… view at source ↗
Figure 6
Figure 6. Figure 6: The subcubic graphs H10 and H18 5.2 Bounds on Ratios In [19] it was noted that if G is nontrivial connected graph then γ(G) ≤ ∆(G)ρ(G). In fact the same reasoning immediately provides the following bound (though we could not find a record of this in the literature). Observation 9 If G is nontrivial connected graph, then γ(G) ≤ ∆(G)γ2(G). It is not hard to find examples of equality, and indeed in the implic… view at source ↗
Figure 7
Figure 7. Figure 7: A 2-tree with γ = 2ρ As regards k-degenerate graphs, Bonamy et al. [2] showed that γ(G)/ρ(G) is unbounded for 3-degenerate graphs. Their example has isolation number 1, but it is readily adapted. Start with the subdivision of the complete graph K2k and add one vertex adjacent to all the subdivision vertices. Then add a perfect matching between the original vertices to yield graph Rk. It can be checked that… view at source ↗
Figure 8
Figure 8. Figure 8: The interval graph ˜I and permutation graph P˜ The bound of Theorem 12b is best possible and indeed so is the implication ι(G) ≤ 4ρL(G). Construct permutation graph P˜ as follows. Start with the permutation graph generated by (3, 6, 1, 8, 5, 2, 9, 4, 7). We observe that vertex v5 has eccentricity 2. Further, permutation graphs are closed under cloning vertices both with the new vertex adjacent to the origi… view at source ↗
read the original abstract

We consider the relationships between the domination number of graph, denoted $\gamma$, and the distance-$2$ domination number, denoted $\gamma_2$, and three parameters that lie between them: the packing number, denoted $\rho$, the lower packing number, denoted $\rho_L$, and the isolation number, denoted $\iota$. There has been recent attention on the question of whether $\gamma/\rho$ is bounded or unbounded for various families of graphs. We consider similar questions for the ratios of the five parameters. In particular we show that, while $\gamma/\rho_L$ is unbounded in trees, it holds that $\iota/\gamma_2$ is less than $2$ for all trees. Further, $\gamma/\rho_L$ is at most $3$ in interval graphs, at most~$4$ in permutation graphs, and at most $5$ in general asteroidal-triple-free graphs. We also show that every tree has a set of vertices that is both isolating and a packing, and characterize trees where $\rho=\rho_L$.

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

0 major / 0 minor

Summary. The manuscript examines relationships among the domination number γ, distance-2 domination number γ₂, packing number ρ, lower packing number ρ_L, and isolation number ι. It establishes that γ/ρ_L is unbounded in trees while ι/γ₂ < 2 holds for every tree; it further proves γ/ρ_L ≤ 3 in interval graphs, ≤ 4 in permutation graphs, and ≤ 5 in asteroidal-triple-free graphs. The paper also shows that every tree admits a vertex set that is simultaneously isolating and a packing, and characterizes the trees satisfying ρ = ρ_L.

Significance. If the stated bounds and existence results hold, the work contributes concrete ratio bounds and a structural theorem connecting isolation and packing in trees, extending the literature on domination parameters in hereditary classes. The AT-free bound and the common isolating-packing set are of particular interest for structural graph theory.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the thorough summary of our results and for the positive recommendation to accept the manuscript. We appreciate the recognition of the ratio bounds in hereditary classes and the structural theorem on isolating packings in trees.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes bounds on ratios of standard domination, packing, and isolation parameters (γ, γ₂, ρ, ρ_L, ι) and an existence result for trees using only the hereditary structural properties of the named graph classes and the conventional definitions of the five parameters. No equations, reductions, or claims reduce any result to a fitted input, self-definition, or self-citation chain; the abstract and stated results are direct consequences of graph-theoretic arguments that remain independent of the paper's own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest entirely on standard definitions and structural properties of the named graph classes; no new entities or fitted constants are introduced.

axioms (2)
  • domain assumption Standard definitions of domination number γ, distance-2 domination γ₂, packing number ρ, lower packing number ρ_L, and isolation number ι hold as in the literature.
    All ratio statements and existence claims presuppose these definitions.
  • domain assumption Trees are acyclic connected graphs; interval, permutation, and asteroidal-triple-free graphs satisfy their usual intersection or forbidden-subgraph characterizations.
    The boundedness results are stated only for these classes.

pith-pipeline@v0.9.1-grok · 5711 in / 1384 out tokens · 47651 ms · 2026-06-26T23:38:27.727496+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

25 extracted references · 5 canonical work pages · 1 internal anchor

  1. [1]

    Adhya, S

    A.S. Adhya, S. Mondal, and S.C. Barman, Minimum vertex-edge dominating set of permutation graphs. Discrete Math. Algorithms Appl. 18 (2026), no. 4, Paper No. 2550055

    2026

  2. [2]

    Bonamy, M

    M. Bonamy, M. Csik´ os, A. Gujgiczer, and Y. Yuditsky, On graph classes with constant domination-packing ratio. Preprint ArXiv 2503.05562 (2025)

    work page arXiv 2025

  3. [3]

    P. Borg, M. Lema´ nska, M. Mora, and M.J. Souto-Salorio, Upper bounds on thek-isolation number. Discrete Math. 349 (2026), 115217

    2026

  4. [4]

    Boutrig, M

    R. Boutrig, M. Chellali, and N. Meddah, Wellve-covered graphs. Commun. Comb. Optim. 10 (2025), 69–78

    2025

  5. [5]

    Boyer and W

    G. Boyer and W. Goddard, Disjoint isolating sets and graphs with maximum isolation number. Discrete Appl. Math. 356 (2024), 10–116

    2024

  6. [6]

    Breˇ sar, T

    B. Breˇ sar, T. Dravec, D.P. Johnston, K. Kuenzel, D.F. Rall, and A. Te- peh, Isolation number: Cartesian and lexicographic products and generalized Sierpi´ nski graphs. Preprint. ArXiv. 2508.16338 (2025). 18

    work page arXiv 2025

  7. [7]

    Bujt´ as, V

    C. Bujt´ as, V. Irˇ siˇ c Chenoweth, S. Klavˇ zar, and G. Zhang, Thed-distance p-packing domination number: complexity, cycles, and trees, Aequationes Math. 100 (2026), no. 2, Paper No. 25

    2026

  8. [8]

    B¨ uy¨ uk¸ colaka, On Well-VE-Dominated Graphs

    Y. B¨ uy¨ uk¸ colaka, On Well-VE-Dominated Graphs. Preprint. Arxiv. 2512.12231 (2025)

    work page arXiv 2025

  9. [9]

    Canales, G

    S. Canales, G. Hern´ andez, M. Martins, and I. Matos, Distance domina- tion, guarding and covering of maximal outerplanar graphs. Discrete Applied Math. 181 (2015), 41–49

    2015

  10. [10]

    Caro and A

    Y. Caro and A. Hansberg. Partial domination — the isolation number of a graph. Filomat 31 (2017), 3925–3944

    2017

  11. [11]

    Cho and M Kim, Independent domination versus packing in subcubic graphs

    E.K. Cho and M Kim, Independent domination versus packing in subcubic graphs. Discrete Appl. Math., 2024

    2024

  12. [12]

    Corneil, S

    D.G. Corneil, S. Olariu, and L. Stewart, Asteroidal triple-free graphs. SIAM J. Discrete Math. 10 (1997), 399–430

    1997

  13. [13]

    D´ ucz and A

    A. D´ ucz and A. Gujgiczer, Domination and packing in graphs. Preprint. ArXiv 2602.18402 (2026)

    work page arXiv 2026

  14. [14]

    Farber, Domination, independent domination, and duality in strongly chordal graphs

    M. Farber, Domination, independent domination, and duality in strongly chordal graphs. Discrete Appl. Math. 7 (1984) 115–130

    1984

  15. [15]

    Goddard and M.A

    W. Goddard and M.A. Henning, The packing number of cubic graphs. Dis- crete Optim. 53 (2024), 100850

    2024

  16. [16]

    Domination in designs

    F. Goldberg, D. Rajendraprasad, and R. Mathew, Domination in designs. Preprint ArXiv:1405.3436 (2014)

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  17. [17]

    G´ omez and J

    R. G´ omez and J. Guti´ errez, Domination and packing in graphs. Discrete Math. 348 (2025), 114393

    2025

  18. [18]

    Hartnell and D.F

    B.L. Hartnell and D.F. Rall, On graphs having one size of maximal open packings, Indian J. Discrete Math. 6 (2020), 1–14

    2020

  19. [19]

    Henning, C

    M.A. Henning, C. L¨ owenstein, and D. Rautenbach, Dominating sets, pack- ings, and the maximum degree. Discrete Math. 311 (2011), 2031–2036. 19

    2011

  20. [20]

    Henning, Packing in trees

    M.A. Henning, Packing in trees. Discrete Mathematics 186 (1998), 145–155

    1998

  21. [21]

    Kostochka and C

    A.V. Kostochka and C. Stocker, A new bound on the domination number of connected cubic graphs. Sib. `Elektron. Mat. Izv. 6 (2009), 465–504

    2009

  22. [22]

    Lewis, S.T

    J.R. Lewis, S.T. Hedetniemi, T.W. Haynes, and G.H. Fricke, Vertex-edge domination. Util. Math. 81 (2010), 193–213

    2010

  23. [23]

    Meir and J.W

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

    1975

  24. [24]

    Tokunaga, T

    S. Tokunaga, T. Jiarasuksakun, and P. Kaemawichanurat, Isolation number of maximal outerplanar graphs. Discrete Appl. Math. 267 (2019), 215–218

    2019

  25. [25]

    Ziemann and P

    R. Ziemann and P. ˙Zyli´ nski, Vertex-edge domination in cubic graphs. Dis- crete Math. 343 (2020), Paper 112075. 20

    2020