pith. sign in

arxiv: 2606.22972 · v1 · pith:OBVZVTFOnew · submitted 2026-06-22 · 🧮 math.CO

On externally supported independence number of graphs

Dragana Bo\v{z}ovi\'c , Iztok Peterin , Adriana Roux , Aleksandra Tepeh This is my paper

Pith reviewed 2026-06-26 08:24 UTC · model grok-4.3

classification 🧮 math.CO
keywords externally supported independence numberisolation numberNP-hardnesstreeslinear-time algorithmgraph boundsindependent setsdomination
0
0 comments X

The pith

A new independence parameter gives an improved upper bound on the isolation number of any graph.

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

The paper defines the externally supported independence number of a graph as the largest independent set B whose neighbors are all dominated by vertices outside the closed neighborhood of B. This quantity is always at most the isolation number, so it supplies a new and sometimes tighter way to upper-bound that quantity. The authors prove that computing the new number is NP-hard on arbitrary graphs yet solvable in linear time on trees. They also give families of sharp bounds that hold for all graphs and for trees, together with complete descriptions of the graphs that attain those bounds.

Core claim

The externally supported independence number α_es(G) is the maximum cardinality of an independent set B such that every vertex in N(B) is dominated by at least one vertex in V(G) - N[B]. This parameter satisfies α_es(G) ≤ ι(G) for every graph G and therefore improves existing upper bounds on the isolation number. Its computation is NP-hard in general but admits a linear-time algorithm on trees; the paper also determines sharp bounds on α_es(G) and completely describes the extremal graphs that achieve them.

What carries the argument

the externally supported independence number α_es(G), the maximum size of an independent set B whose open neighborhood N(B) is dominated from outside the closed neighborhood N[B]

If this is right

  • The isolation number of every graph is at most its externally supported independence number.
  • Computing the externally supported independence number is NP-hard on general graphs.
  • A linear-time algorithm computes the externally supported independence number on trees.
  • Several families of graphs attain the derived upper and lower bounds exactly.

Where Pith is reading between the lines

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

  • The linear-time algorithm on trees suggests the parameter may be tractable on other recursively structured classes such as series-parallel graphs.
  • The external-domination requirement could be relaxed or strengthened to produce additional variants that bound other domination-type numbers.
  • Comparing the new parameter with the ordinary independence number on random graphs would show how often the bound is strictly tighter.
  • The extremal-graph characterizations may help decide whether the parameter equals the isolation number on particular graph families.

Load-bearing premise

The external-domination condition on N(B) produces a quantity that is always at most the isolation number but sometimes strictly smaller than the ordinary independence number.

What would settle it

Any graph G in which the isolation number ι(G) is strictly larger than the externally supported independence number α_es(G) would falsify the claimed upper bound.

Figures

Figures reproduced from arXiv: 2606.22972 by Adriana Roux, Aleksandra Tepeh, Dragana Bo\v{z}ovi\'c, Iztok Peterin.

Figure 1
Figure 1. Figure 1: The graph M(C5, K6). We first show that every independent set of H is an ESI-set of G. Let A ⊆ V (H) be independent. If vi ∈ N(A), then its matched neighbor ui ∈/ N[A]. Similarly, if uj ∈ N(A), then vj ∈ A, and uj has a neighbor uℓ ∈/ N[A], since ℓ > n(H) and uℓ has no neighbors in H. Therefore, A satisfies the ES-condition. In particular, every α(H)-set is an ESI-set of G, and hence αes(G) ≥ α(H) ≥ 2. Nex… view at source ↗
Figure 2
Figure 2. Figure 2: A graph G showing that condition (ii) is necessary. Next, we present an upper bound that depends on δ(G), ∆(G) and n(G). Two direct consequences follows, one for k-regular graphs where ∆(G) = δ(G) = k and one for trees where δ(T) = 1. 10 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: For each support vertex w ∈ S(x) choose exactly one leaf tw ∈ L(w), and define B x = (B ′ − {tw : w ∈ S(x)}) ∪ (L(x) − {tx}) and Dx = ((D′ − {x}) − (L(x) − {tx})) ∪ {tw : w ∈ S(x)}. Again, Dx dominates N(Bx ) and thus Bx is an ESI-set. L(x) . . . x S(x) . . . . . . . . . switch at x reverse switch at x L(x) . . . x S(x) . . . . . . . . [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Trees in A ∪ B ∪ C. Let A be the family of trees constructed as follows. Start with a star K1,t, where t ≥ 2, with center x. For each leaf v of this star, attach kv ≥ 1 new leaves to v. To construct a tree T in the family B, start with a star K1,t, where t ≥ 2, with center x. For each leaf v with the exception of precisely one leaf y of this star, attach kv ≥ 1 new leaves to v (i.e., among the neighbors of… view at source ↗
read the original abstract

We introduce the \emph{externally supported independence number} $\alpha_{\rm es}(G)$ of a graph $G$ as the maximum cardinality of an independent set $B$ with an additional condition, that vertices from $N(B)$ are dominated by vertices in $V(G)-N[B]$. This parameter yields an improved upper bound on the isolation number $\iota(G)$. We show that computing $\alpha_{\rm es}(G)$ is NP-hard, while for trees we present a linear-time algorithm. We also establish several sharp bounds on $\alpha_{\rm es}(G)$ for general graphs, with additional refined results for trees. In several cases, we completely describe the extreme graph classes attaining these bounds.

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 / 1 minor

Summary. The paper introduces the externally supported independence number α_es(G) as the maximum size of an independent set B in G such that N(B) is dominated by V(G) − N[B]. It shows that α_es(G) yields an improved upper bound on the isolation number ι(G), proves that computing α_es(G) is NP-hard, provides a linear-time algorithm for trees, and establishes several sharp bounds on α_es(G) for general graphs and trees, including complete characterizations of extremal graphs in some cases.

Significance. The new parameter is internally consistent with the domination condition and directly improves the bound on ι(G) without circularity. The NP-hardness reduction and tree DP algorithm are standard and correctly scoped; extremal bounds are supported by explicit constructions. These elements strengthen the contribution if the proofs hold as described.

minor comments (1)
  1. The abstract and introduction would benefit from an explicit small example (e.g., a cycle or path) illustrating the difference between α_es(G) and α(G) to clarify the external-support condition.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, the clear summary of its contributions, and the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper defines α_es(G) explicitly as the max |B| where B is independent and N(B) is dominated by V(G)-N[B]. The claimed upper bound on ι(G) follows directly from comparing the two definitions (no fitting, no self-citation chain, no imported uniqueness theorem). NP-hardness reduction and tree algorithm are standard algorithmic arguments with no parameter reuse. No equations or steps reduce by construction to their own inputs; the parameter is introduced independently and the extremal results rest on explicit constructions and proofs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities can be extracted beyond the standard graph-theoretic background assumed in the definition.

pith-pipeline@v0.9.1-grok · 5652 in / 975 out tokens · 18673 ms · 2026-06-26T08:24:37.421442+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

21 extracted references · 1 canonical work pages

  1. [1]

    Adabi, E.E

    M. Adabi, E.E. Targhi, N. Jafari Rad, and M.S. Moradi. Properties of independent Roman domination in graphs.Australas. J. Combin., 52:11–18, 2012

    2012

  2. [2]

    Bartolo, P

    K. Bartolo, P. Borg, and D. Scicluna. Isolation of squares in graphs.Discrete Math., 347(12):Paper No. 114161, 11, 2024

    2024

  3. [3]

    P. Borg. Isolation of cycles.Graphs Combin., 36(3):631–637, 2020

    2020

  4. [4]

    Božović, A

    D. Božović, A. Kelenc, I. Peterin, and I.G. Yero. Incidence dimension and 2-packing number in graphs.RAIRO Oper. Res., 56(1):199–211, 2022

    2022

  5. [5]

    Boyer and W

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

    2024

  6. [6]

    Boyer and W

    G. Boyer and W. Goddard. Bounds on independent isolation in graphs.Discrete Appl. Math., 372:143–149, 2025

    2025

  7. [7]

    Boyer, W

    G. Boyer, W. Goddard, and M.A. Henning. On total isolation in graphs.Aequationes Math., 99(2):623–633, 2025

    2025

  8. [8]

    Brešar, T

    B. Brešar, T. Dravec, D.P. Johnston, K. Kuenzel, D.F. Rall, and A. Tepeh. Isola- tion number: Cartesian and lexicographic products and generalized sierpiński graphs. arXiv:2508.16338v1, 2025

    work page arXiv 2025

  9. [9]

    Cabrera Martinez, I

    A. Cabrera Martinez, I. Peterin, and I.G. Yero. Independent transversal total dom- ination versus total domination in trees.Discuss. Math. Graph Theory, 41:213–224, 2021. 20

    2021

  10. [10]

    Caro and A

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

    2017

  11. [11]

    S. Chen, Q. Cui, and L. Zhong. A characterization of graphs with maximumk-clique isolation number.Discrete Math., 348(9):Paper No. 114531, 13, 2025

    2025

  12. [12]

    Cockayne, P.A

    E.J. Cockayne, P.A. Dreyer, Jr., S.M. Hedetniemi, and S.T. Hedetniemi. Roman dom- ination in graphs.Discrete Math., 278(1-3):11–22, 2004

    2004

  13. [13]

    Courcelle

    B. Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs.Inform. Comput., 85(1):12–75, 1990

    1990

  14. [14]

    Lineartimesolvableoptimizationproblems on graphs of bounded clique-width.Theory Comput

    B.Courcelle, J.A.Makowsky, andU.Rotics. Lineartimesolvableoptimizationproblems on graphs of bounded clique-width.Theory Comput. Systems, 33(2):125–150, 2000

    2000

  15. [15]

    Garey and D.S

    M.R. Garey and D.S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979

    1979

  16. [16]

    Haynes, S.T

    T.W. Haynes, S.T. Hedetniemi, and M.A. Henning.Domination in graphs: Core con- cepts. Springer, 2023

    2023

  17. [17]

    Lemańska, M

    M. Lemańska, M. Mora, and M.J. Souto-Salorio. Graphs with isolation number equal to one third of the order.Discrete Math., 347(5):Paper No. 113903, 10, 2024

    2024

  18. [18]

    Lemańska, M.J

    M. Lemańska, M.J. Souto-Salorio, A. Dapena, and F.J. Vazquez-Araujo. Isolation number versus domination number of trees.Mathematics, 9(12):1325, 2021

    2021

  19. [19]

    Lewis, S.T

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

    2010

  20. [20]

    Ziemann and P

    R. Ziemann and P. Żyliński. Vertex-edge domination in cubic graphs.Discrete Math., 343(11):112075, 14, 2020

    2020

  21. [21]

    Żyliński

    P. Żyliński. Vertex-edge domination in graphs.Aequationes Math., 93(4):735–742, 2019. 21

    2019