Pith. sign in

REVIEW 2 minor 18 references

On the minimum number of maximal distance-$k$ independent sets in trees

T0 review · 0 major / 2 minor · reviewed 2026-05-07 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The minimum number of maximal distance-k independent sets over all n-vertex trees is n if n ≤ k+1, and n minus floor((n minus k mod 2) divided by floor(k/2) plus 1) plus 1 otherwise.

desk verdict The paper gives a closed-form minimum for the number of maximal distance-k independent sets over all n-vertex trees plus a full characterization of the trees that hit it. read the letter →

arxiv 2604.27424 v1 submitted 2026-04-30 math.CO

Dmitrii Taletskii This is my paper · ORCID
classification math.CO
keywords treesdistance-kindependentsetsmaximalextremalenumerationminimumnumber
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper determines the smallest possible number of inclusion-maximal distance-k independent sets that any tree on n vertices must contain, for arbitrary positive integers n and k. Distance-k independent sets are vertex subsets in which every pair lies at distance at least k+1, so their maximal versions are the largest possible spread-out collections under that spacing rule. Establishing the exact minimum reveals how tree shapes can be arranged to support as few such collections as possible. The authors supply a closed arithmetic formula for the minimum together with a complete list of the trees that meet it, and they track how many non-isomorphic copies of those trees exist as n grows.

What carries the argument

The closed-form arithmetic expression that subtracts a roughly n divided by (k/2) term from n, adjusted by parity, together with the explicit family of trees built from repeated path segments of length governed by k that realize the fewest maximal distance-k sets.

What would settle it

Any n-vertex tree, for concrete n and k satisfying the conditions, whose exact count of inclusion-maximal distance-k independent sets falls strictly below the number given by the formula.

Watch

Extended reading notes

Core claim

For all n, k ≥ 1 the minimum possible number of inclusion-wise maximal distance-k independent sets in an n-vertex tree equals n when n ≤ k+1 and equals n minus floor of (n minus (k mod 2)) divided by (floor(k/2) plus 1), plus 1, otherwise. The trees attaining this bound are fully described, and the number of non-isomorphic n-vertex trees achieving the minimum either grows linearly with n or is bounded above by the number of unlabeled trees on k squared vertices, depending on the parity of k and whether (k+1)/2 divides n-1.

Load-bearing premise

The case analysis or inductive construction that derives the formula correctly accounts for every possible tree structure and does not miss any configuration that could support fewer maximal distance-k independent sets.

Editorial extensions

If this is right

  • The bound is attained by particular families of trees whose structure is completely classified.
  • When k is odd and (k+1)/2 does not divide n-1 the number of non-isomorphic extremal trees grows linearly with n.
  • In all other cases the number of such trees on n vertices stays bounded by a constant that depends only on k.
  • The formula yields the exact minimum without requiring enumeration of all trees.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The linear-growth regime implies that extremal trees differ mainly by the placement of a bounded number of local modifications along a long path backbone.
  • The bounded-growth regime implies that for sufficiently large n all extremal trees are assembled from a fixed finite repertoire of k-dependent blocks.
  • The explicit tree descriptions make it feasible to generate or recognize all minimal trees in linear time for the bounded case.
  • The same spacing-minimization idea could be tested on other sparse graphs such as unicyclic graphs to see whether trees remain the absolute minimizers.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The manuscript determines the minimum possible number of inclusion-wise maximal distance-k independent sets over all n-vertex trees for given n and k. The minimum is n for n ≤ k + 1, and n − ⌊(n − (k mod 2)) / (⌊k/2⌋ + 1)⌋ + 1 otherwise. The authors provide a complete description of the trees achieving this bound and analyze the growth rate of the number of such trees for fixed k.

Significance. If the result holds, it is a notable achievement in extremal combinatorics on trees, delivering an exact formula without free parameters and a full structural characterization of the extremal family. The growth rate result, showing linear growth or bounded by the number of k²-vertex trees depending on divisibility conditions, adds depth to the contribution. The authors are credited for the parameter-free closed form and the explicit description of attaining trees.

minor comments (2)
  1. The abstract and introduction present the formula clearly, but the body should include a short table of small (n,k) values (e.g., k=1,2,3 and n up to 10) to allow immediate verification of the claimed minimum.
  2. In the growth-rate section, the distinction between the linear-growth case and the bounded case is stated, but an explicit reference to the relevant theorem number when invoking the k²-vertex tree bound would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our manuscript, the assessment of its significance in extremal combinatorics on trees, and the recommendation for minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; combinatorial minimum derived via explicit construction and exhaustive case analysis

full rationale

The paper states a closed-form minimum for the number of maximal distance-k independent sets in trees and completely describes the attaining trees. This rests on direct combinatorial arguments (inductive removal of leaves or paths, parity-based decomposition) that construct the bound and prove it is tight, without any self-definitional reduction, fitted parameters renamed as predictions, or load-bearing self-citations. The formula is presented as the outcome of the analysis rather than an input to it, and the growth-rate statement follows from the same structural classification. No step reduces the claimed result to its own inputs by construction.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The result relies on standard graph-theoretic definitions without introducing free parameters, new entities, or non-standard axioms.

assumptions (1)
  • standard math Standard definitions of graphs, trees, vertex distance, and independent sets
    The paper builds directly on these foundational concepts from graph theory.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the minimum number of maximal distance-$k$ independent sets in trees." pith.science (2026). https://pith.science/paper/2604.27424

@misc{pith2026260427424,
  author       = {Pith},
  title        = {Pith review of: On the minimum number of maximal distance-$k$ independent sets in trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2604.27424}},
  note         = {Machine review of arXiv:2604.27424}
}
abstract

A vertex subset of a graph is called a distance-$k$ independent set if the distance between any two of its distinct vertices is at least $k + 1$. For all $n,k \geq 1$, we determine the minimum possible number of inclusion-wise maximal distance-$k$ independent sets among all $n$-vertex trees. It equals $n$ if $n \leq k + 1$, and $n - \bigg\lfloor \frac{n - (k \bmod 2)}{\lfloor k/2 \rfloor + 1} \bigg\rfloor + 1$ otherwise. We also completely describe the class of trees attaining this bound and determine the growth rate of the number of such $n$-vertex trees for a fixed $k \geq 1$. If $k$ is odd and $(k+1)/2$ does not divide $n-1$, then the number of non-isomorphic $n$-vertex trees with the minimum possible number of maximal distance-$k$ independent sets grows linearly with $n$. Otherwise, it is bounded above by the number of unlabeled $k^2$-vertex trees.

Figures

Figures reproduced from arXiv: 2604.27424 by the authors.

Figure 1
Figure 1. The family B5,2. Let T be a tree and let k ≥ 2. A vertex u ∈ V (T) is a k-twin if there exists a vertex v ∈ V (T) \ {u} such that Nk[u] = Nk[v]. A pair of vertices (x, y) is k-special if x and y are diametral leaves that are both k-twins, but Nk[x] ̸= Nk[y]. A vertex is called a diametral k-twin if it is a diametral leaf and a k-twin. Let T be an n-vertex tree with no diametral k-twins for some k ≥ 2, and let r ≥ 0.… view at source ↗
Figure 2
Figure 2. The family Add∗ 2 (S ′ 3,2 , 1). Let T be a tree with a leaf ℓ. Let mdik(T) denote the total number of k-MDISs of T. Let mdi∗ k (T, ℓ) denote the number of k-MDISs J of T with the following property: ℓ ∈ J and there exists a vertex w ∈ V (T) \ J such that Nk[w] ∩ J = {ℓ}. Let Mk(T) denote the family of all k-MDISs of T. Let k ≥ 2 and m ≥ 1. If a tree T ′ can be obtained from a tree T by deleting a k-twin leaf of T, … view at source ↗
Figure 3
Figure 3. Examples of trees from the family Add4(S ′ 5,3 , 2). 4.2 Odd k ≥ 3 Recall that every n-vertex tree with diameter at most k (in particular, with at most k + 1 vertices) has exactly n k-MDISs. Lemma 15. Let T be an n-vertex tree of diameter k + 1 with n = p ·(⌊k/2⌋+ 1) +r + 1, where p ≥ 2 and 0 ≤ r ≤ ⌊k/2⌋. Then mdik(T) ≥ fk(n) with equality if and only if T ∈ Add∗ k (Sp,⌊k/2⌋+1, r). Proof. We apply induction on n. Th… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: All non-isomorphic 3-minimal 8-vertex trees. Finally, we show that if a k-minimal tree is not unique, then there are linearly many such trees. Theorem 4. For all odd k ≥ 3 and all n ≥ 4, if (k+1)/2 does not divide n−1, then the number of non-isomorphic n-vertex k-minim…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Miller, D.E

    R.E. Miller, D.E. Muller, A problem of maximum consistent subsets, IBM Research Report RC-240, J.T. Watson Research Center, New York, USA, 1960

    work page 1960

  2. [2]

    J.W. Moon, L. Moser, On cliques in graphs, Isr. J. Math. 3 (1965) 23–28

    work page 1965

  3. [3]

    F¨ uredi, The number of maximal independent sets in connected graphs, J

    Z. F¨ uredi, The number of maximal independent sets in connected graphs, J. Graph Theory 11 (1987) 463–470

    work page 1987

  4. [4]

    Griggs, C.M

    J.R. Griggs, C.M. Grinstead, D.R. Guichard, The number of maximal independent sets in a connected graph, Discrete Math. 68 (1988) 211–220

    work page 1988

  5. [5]

    Hujter, Z

    M. Hujter, Z. Tuza, The number of maximal independent sets in triangle-free graphs, SIAM J. Discrete Math. 6 (1993) 284–288

    work page 1993

  6. [6]

    Koh, C.Y

    K.M. Koh, C.Y. Goh, F.M. Dong, The maximum number of maximal independent sets in unicyclic connected graphs, Discrete Math. 308 (2008) 3761–3769

    work page 2008

  7. [7]

    Liu, Constraints on the number of maximal independent sets in graphs, J

    J. Liu, Constraints on the number of maximal independent sets in graphs, J. Graph Theory 18 (1994) 195–204

    work page 1994

  8. [8]

    Wilf, The number of maximal independent sets in a tree, SIAM J

    H.S. Wilf, The number of maximal independent sets in a tree, SIAM J. Algebr. Discrete Methods 7 (1986) 125–130

    work page 1986

Show all 18 references
  1. [9]

    Sagan, A note on independent sets in trees, SIAM J

    B.E. Sagan, A note on independent sets in trees, SIAM J. Discrete Math. 1 (1988) 105–108

    1988

  2. [10]

    Chang and M.J

    G.J. Chang and M.J. Jou. The number of maximal independent sets in connected triangle-free graphs. Discrete Math. 197 (1999) 169–178

    1999

  3. [11]

    Trees without twin-leaves with the smallest num- ber of maximal independent sets

    D.S.Taletskii and D.S.Malyshev. Trees without twin-leaves with the smallest num- ber of maximal independent sets. Diskret. Mat. 30:4 (2018) 115–134

    2018

  4. [12]

    The Minimum Number of Maximal Independent Sets in Twin-Free Graphs

    S.Cambie, S.Wagner. The Minimum Number of Maximal Independent Sets in Twin-Free Graphs. The Electronic Journal of Combinatorics. 31 (2024). P4.71

    2024

  5. [13]

    Journal of Applied and Industrial Mathematics

    D.S.Taletskii On Trees with a Given Diameter and the Extremal Number of Distance-kIndependent Sets. Journal of Applied and Industrial Mathematics. 17:3 (2023) 664–677

    2023

  6. [14]

    Merri- field–Simmons index and minimum number of independent sets in short trees

    A.Frendrup, A.S.Pedersen, A.A.Sapozhenko, P.D.Vestergaard, “Merri- field–Simmons index and minimum number of independent sets in short trees”, Ars Combin., 111 (2013). 85–95

    2013

  7. [15]

    Trees of Diameter 6 and 7 with Minimum Number of Independent Sets

    D.Taletskii. Trees of Diameter 6 and 7 with Minimum Number of Independent Sets. Math. Notes. 109 (2021) 280–291

    2021

  8. [16]

    Discussiones Mathematicae Graph Theory

    R.Euler, P.Oleksik, Z.Skupie´ n, Counting Maximal Distance-Independent Sets in Grid Graphs. Discussiones Mathematicae Graph Theory. 33:3 (2013) 531–557

    2013

  9. [17]

    Self-stabilizing algorithms for computing maximal distance-2 independent sets and minimal dominating sets in networks

    D.Bouhata, S.Bouam, H.Moumen, B.Benreguia, C.Arar. Self-stabilizing algorithms for computing maximal distance-2 independent sets and minimal dominating sets in networks. Ing´ enierie des Syst` emes d’Information. 29(2) (2024) 581–590

    2024

  10. [18]

    Distance-dindependent set problems for bipartite and chordal graphs

    H.Eto, F.Guo, E.Miyano. Distance-dindependent set problems for bipartite and chordal graphs. Journal of Combinatorial Optimization. 27:1 (2014) 88–99

    2014

Pith tools

Reviewed May 7, 2026 · model on record in the stance chip above.