A conjecture on different central parts of binary trees

Dinesh Pandey; Kamal Lochan Patra

REVIEW 4 major objections 4 minor 15 references

A conjecture on different central parts of binary trees

T0 review · 4 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that among all binary trees on n vertices, the pairwise distances between the center, centroid, and subtree core are maximized by a crg tree, and it identifies the exact maximizing crg trees for each pair.

desk verdict The conjecture proof and the crg maximizers are credible, but the main reduction leans on an unproved monotonicity claim about the center that a referee should push the authors to formalize. read the letter →

arxiv 2009.12066 v1 pith:TVAQM62Y submitted 2020-09-25 math.CO

Dinesh Pandey , Kamal Lochan Patra This is my paper · ORCID

classification math.CO MSC 05C0505C1205C35

keywords binarytreescentercentroidsubtreecorecrgextremaldistancesroot-containingsubtreesrgood

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

This paper settles a conjecture about how far apart a tree's three notions of "middle" can be. For binary trees on $n\ge 12$ vertices, it proves that the distance between the center and the centroid, the distance between the center and the subtree core, and the distance between the centroid and the subtree core are each maximized by some crg tree: the tree formed by grafting an rgood binary tree onto the end of a binary caterpillar. It then names the precise crg trees that achieve the maximum in each case: for center versus centroid the tree $T_{rg}^{n,l}$ with $l=2\lceil n/4\rceil+1$, and for the two subtree-core distances the crg tree whose rgood part has the smallest positive odd order $l$ satisfying $f_{T_{rg}^l}(r)>3\cdot 2^{(n-l-1)/2}-2$. The upshot is a complete answer to which binary trees spread their central parts farthest apart, with explicit upper bounds for every $n$.

What carries the argument

The load-bearing object is the crg tree $T_{rg}^{n,l}$, formed by identifying the root of an rgood binary tree with a vertex of maximum eccentricity of a binary caterpillar. The argument runs through cut-edge comparisons. Lemma 2.3 says the centroid lies on the side of an edge with the larger number of vertices; Lemma 2.6 says the subtree core lies on the side whose rooted component has more root-containing subtrees. These let the authors replace the side away from the target central part by $T_{rg}^k$ (maximizing root-containing subtrees) or by $T_{r,2}^l$ (the two-vertices-per-level tree, minimizing them), moving the center outward along every longest path while keeping the centroid or subtree core on the intended side. A double-exponential recurrence $A_h=(A_{h-1}+1)^2$, whose solution is $\lfloor k^{2^h}\rfloor-1$ with $k=2.25851845\ldots$, pins down the threshold $l$ for the subtree-core maximizers.

What would settle it

Enumerate all binary trees on $n=12,14,16,18,20$, compute $d(C,Cd)$, $d(C,Sc)$, and $d(Cd,Sc)$ for each, and check that the maximum equals the value attained by the paper's specified crg tree; a single binary tree exceeding the claimed crg maximum, or one replacement step in the proof that moves the centroid or subtree core across the cut edge, would falsify the theorem.

Watch

Extended reading notes

Core claim

The central claim is that the extremal shapes for central-part distances in binary trees are crg trees. Writing $C(T)$, $Cd(T)$, and $Sc(T)$ for the center, centroid, and subtree core, the paper proves in Theorems 3.1, 3.4, and 3.11 that for every binary tree $T$ on $n$ vertices there is a crg tree $T'$ with $d_{T'}(C,Cd)\ge d_T(C,Cd)$, $d_{T'}(C,Sc)\ge d_T(C,Sc)$, and $d_{T'}(Cd,Sc)\ge d_T(Cd,Sc)$. The exact maximizers are then identified: for center versus centroid it is the crg tree with $l=2\lceil n/4\rceil+1$, and for the two subtree-core distances it is the crg tree whose rgood part has smallest odd order $l$ satisfying $f_{T_{rg}^l}(r)>3\cdot 2^{(n-l-1)/2}-2$. The paper also records explicit upper bounds, such as $d_T(C,Cd)\le \lfloor n/4\rfloor - \lfloor (\lfloor n/4\rfloor+1+h)/2\rfloor$, where $h$ is the smallest positive integer with $\lceil n/4\rceil\le 2^h-1$.

Load-bearing premise

The transformation arguments in Theorems 3.1, 3.4, and 3.11 assume that replacing a component by an rgood tree or by the two-vertices-per-level tree keeps the centroid or subtree core on the same side of the cut edge and moves the center away from that side; if any such replacement pulled a central part across the cut, the crg-maximizer conclusion would not follow.

Editorial extensions

If this is right

For every binary tree on $n$ vertices, $d(C,Cd)\le \lfloor n/4\rfloor-\lfloor(\lfloor n/4\rfloor+1+h)/2\rfloor$, where $h$ is the least integer with $\lceil n/4\rceil\le 2^h-1$, and equality holds exactly at the crg tree $T_{rg}^{n,l}$ with $l=2\lceil n/4\rceil+1$.
The maximum distances involving the subtree core are attained at the crg tree whose rgood part has smallest odd order $l$ satisfying $f_{T_{rg}^l}(r)>3\cdot 2^{(n-l-1)/2}-2$; small cases checked in the paper show these maxima are $0$ for $n=12,16$ and become positive from $n=14$ or $20$ onward depending on $n$ modulo $4$.
The center-centroid maximizer and the subtree-core maximizers are generally different crg trees, so no single binary tree maximizes all three pairwise distances at once.
Proposition 2.13 stands on its own: among rooted binary trees on $n$ vertices, the two-vertices-per-level tree $T_{r,2}^n$ minimizes the number of root-containing subtrees, complementing the known maximizing tree $T_{rg}^n$.

Reading between the lines

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

Because the cut-side lemmas compare component sizes and root-containing-subtree counts, the same two-step replacement likely transfers to other median-type central parts of trees that are defined by component-count inequalities, yielding analogous crg-maximizer theorems.
The recurrence solution $A_h=\lfloor k^{2^h}\rfloor-1$ with $k=2.25851845\ldots$ makes the threshold $l$ in Theorems 3.9 and 3.12 computable in principle; deriving its asymptotic growth would give closed-form rates for the maximum center-subtree-core and centroid-subtree-core distances, which the paper leaves implicit.
The paper bounds $f_{T_{rg}^l}(r)$ between consecutive complete-tree values rather than computing it exactly; a sharper evaluation of that count would let the threshold $l$, and hence all three maximum distances, be written purely as a function of $n$.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: The central claim is that the extremal shapes for central-part distances in binary trees are crg trees. Writing $C(T)$, $Cd(T)$, and $Sc(T)$ for the center, centroid, and subtree core, the paper proves in Theorems 3.1, 3.4, and 3.11 that for every binary tree $T$ on $n$ vertices there is a crg tree $T'$ with $d_{T'}(C,Cd)\ge d_T(C,Cd)$, $d_{T'}(C,Sc)\ge d_T(C,Sc)$, and $d_{T'}(Cd,Sc)\ge d_T(Cd,Sc)

/-- @claim 1 The central claim is that the extremal shapes for central-part distances in binary trees are crg trees. Writing $C(T)$, $Cd(T)$, and $Sc(T)$ for the center, centroid, and subtree core, the paper proves in Theorems 3.1, 3.4, and 3.11 that for every binary tree $T$ on $n$ vertices there is a crg tree $T'$ with $d_{T'}(C,Cd)\ge d_T(C,Cd)$, $d_{T'}(C,Sc)\ge d_T(C,Sc)$, and $d_{T'}(Cd,Sc)\ge d_T(Cd,Sc) -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Short version: this paper does what the abstract promises — it proves the Smith et al. conjecture on the maximizers of pairwise distances among center, centroid, and subtree core for binary trees, and it names the exact maximizers (the crg trees). Proposition 2.13, the minimizer of root-containing subtrees, is also new and has a real exchange proof. This is not a new framework; it extends the program in [3,10,11], but the conjecture was open and the explicit extremal trees are new. The Aho–Sloane computation for the recurrence in Section 2.2 is a useful concrete touch.

The soft spots are concentrated in the reduction. In Theorems 3.1, 3.4, and 3.11, the argument replaces a component by T^k_rg, or moves leaves stepwise, and asserts that the center (or centroid) "either stays the same or moves away from v." Lemma 2.1 only compares heights of rooted trees; it does not control the eccentricity function on the other component. The stress-test note is right: this is a genuine gap in the main reduction, not a style complaint. The intuition is sound and the direction of the inequality is the right one, so it is probably fillable — but the monotonicity of the center under these replacements needs its own lemma, especially for the second replacement by the two-per-level tree, which changes the internal eccentricity function rather than just shifting it. Theorem 3.11's stepwise centroid claim is the same pattern.

Two smaller issues. Theorem 3.2's Case II (n = 4k+2) is dismissed as "similar," while Case I is long and case-heavy; one sentence is not enough. And several "it can be checked" assertions (the centroid of small crg trees, the n ≤ 16 checks, the n = 14 and n = 20 checks) are not shown; minor individually, but a referee should ask for details. The implicit definition of l in Theorems 3.9 and 3.12 is unusual but not circular, and the citation pattern is fine.

Bottom line: the result is real, the gaps are identifiable and likely fixable, and the paper deserves a serious referee. Send it out, with a request for a proof of the monotonicity lemma and the missing case.

Referee Report

4 major / 4 minor

Summary. The paper studies the three classical centrality measures on binary trees—center, centroid, and subtree core—and the pairwise distances between them. It proves a conjecture attributed to Smith, Székely, Wang, and Yuan: among all binary trees on n vertices, each of the three pairwise distances is maximized by some tree in the family Ω_n of 'crg' trees, obtained by identifying the root of an rgood binary tree with an end vertex of a binary caterpillar. The proof proceeds by a two-step replacement argument (Theorems 3.1, 3.4, 3.11) that transforms an arbitrary extremal candidate into a crg tree without decreasing the relevant distance, and then by a case analysis over crg trees to identify the exact maximizers (Theorems 3.2, 3.9, 3.12). Along the way the paper proves Proposition 2.13, that among rooted binary trees on n vertices the tree T^n_{r,2} with exactly two vertices per level minimizes the number of root-containing subtrees, and gives a closed form for the recurrence satisfied by the number of root-containing subtrees of complete rgood trees.

Significance. If the proof is completed, the paper resolves the stated conjecture and gives explicit extremal trees and distance formulas (Corollary 3.3 and the accompanying bounds). The paper is self-contained: the auxiliary results, especially Lemma 2.3 and Lemma 2.6 relating the side of a cut edge to the centroid and subtree core, and Proposition 2.13 on the minimization of root-containing subtrees, are clean and of independent interest. The exact formulas are parameter-free and checkable. However, as detailed below, several load-bearing monotonicity assertions about the movement of the center and centroid under tree surgery are not proved; the current manuscript therefore does not yet fully justify its central claim.

major comments (4)

[Section 3.1, proof of Theorem 3.1] The proof asserts 'Also by Lemma 2.1, ht(Te(v)) ≥ ht(T^k_rg). So C(T') either same as C(T) or moves away from the vertex v.' This does not follow from Lemma 2.1, which only compares the heights of the two rooted components, not the full eccentricity functions of vertices in the rest of the tree. For a vertex x in the center-side component, e_T(x) is the maximum of d(x,v)+1+ht(Te(v)) and the eccentricity of x within that component; reducing the height lowers only the first of these two terms, and the center could in principle shift into the newly inserted rgood tree if that tree is sufficiently compact. This monotonicity is essential for the conclusion d_{T'}(C,Cd) ≥ d_T(C,Cd), so it must be proved as a separate lemma or replaced by a different argument.
[Section 3.2, proof of Theorem 3.4] The identical issue appears in the proof of Theorem 3.4: the sentence 'Also by Lemma 2.1, ht(Te(v)) ≥ ht(T^k_rg). So C(T') either same as C(T) or moves away from the vertex v' is used without proof. The later assertion that after replacing the center-side component with T^l_{r,2} the center 'moves away from v' is also stated without an eccentricity calculation, even though this second replacement changes the internal eccentricity function of the component rather than merely shifting one term. These points are load-bearing for the inequality d_{T''}(C,Sc) ≥ d_T(C,Sc).
[Section 3.3, proof of Theorem 3.11] The stepwise transformation of T'_{e2}(v') into T^l_{r,2} is justified by the assertion 'in each step the centroid is either same as the centroid of the tree in the previous step or moves away from v,' but no proof is supplied. Moving two pendant leaves can change the sizes of branches at many vertices, and the centroid could shift toward v for some intermediate tree. Since this is the mechanism for d_{T''}(Cd,Sc) ≥ d_T(Cd,Sc), a detailed weight analysis is needed.
[Sections 3.1 and 3.2, Theorems 3.2 and 3.9] Theorem 3.2 dismisses the case n = 4k+2 with 'A similar argument can be given,' even though the exact maximizing crg tree is part of the paper's contribution. Similarly, Theorem 3.9 relies on several 'it can be checked' assertions for specific trees (T^{14,7}_{rg}, T^{20,11}_{rg}, and the n=12,16 cases) that anchor the α=0 analysis. These finite checks and the omitted case should be supplied, since the correctness of the extremal characterizations depends on them.

minor comments (4)

[Throughout] There are numerous typos: 'caterpilar' appears repeatedly (e.g., Section 1.1, proof of Lemma 2.2, Theorem 3.5), 'cehecked' in the proof of Theorem 3.9, 'postive' in Corollaries 3.10 and 3.12, and 'recuurence' in Section 2.1.
[Section 2.2] The displayed formulas 'Y_h = ⌊k2^h⌋' and 'A_h = ⌊k2^h⌋ − 1' appear to be missing a superscript: the Aho-Sloane solution is of the form ⌊k^{2^h}⌋. Please correct the typesetting.
[Section 2.1, Proposition 2.13] The tree T^n_{r,2} is described only by the phrase 'with exactly two vertices at every level (except zero level)'; it would be clearer to spell out its structure as a rooted binary tree consisting of a spine of length (n−1)/2 with one extra pendant vertex at each internal spine vertex, which is what the later proof uses.
[Theorem 3.9, proof] The finite checks in Case II ('it can be checked that C(T^{14,7}_{rg}) = {4} and Sc(T^{14,7}_{rg}) = {5}', and the analogous checks for T^{20,11}_{rg} and the n=12,16 cases) would be more transparent if presented in a small table, especially because they are used to rule out the α=0 regime for all larger n of the same congruence class.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular dependency; the proof is a direct extremal construction with independent external lemmas, and the noted gaps are proof-strength issues, not circularity.

full rationale

The paper proves the Smith et al. conjecture directly rather than assuming it. The extremal rooted-tree facts it needs are either proved in the paper (Lemma 2.1, Proposition 2.13, Corollary 2.14) or cited from independent external sources (Proposition 1.2 from Harary, Proposition 1.3 and Lemma 1.4 from Székely–Wang, Proposition 2.11 from Smith et al.). The cited maximization of root-containing subtrees is external, and the minimization result is new and proved, so the proof does not reduce to the conjecture being established. The threshold l in Theorems 3.9 and 3.12 is defined by an inequality involving R_l and n, not fitted to the target distances, so the maximizing tree is not a renamed fitted parameter. The construction of crg trees via replacement is not circular: the rgood tree and T_{r,2} are independently characterized extremal trees, and the proof then uses component-size and subtree-count comparisons. The only substantive weakness is the informally asserted monotonicity that replacing a component with an rgood tree or with T_{r,2} moves the center away from the cut (Theorems 3.1, 3.4, 3.11); this is an unproved step and a correctness risk, but it does not make the conclusion equivalent to the assumptions by construction. No self-citation chain is load-bearing, and no prediction is identical to an input. Thus the circularity score is 0.

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

The paper introduces no new entities and fits no free parameters. It relies on standard external results for center/centroid structure, subtree core structure, and the maximality of rgood trees for root-containing subtrees.

assumptions (5)

standard math Center and centroid of a tree each consist of either a single vertex or two adjacent vertices.
Cited as Proposition 1.2 from [5]; used throughout to reason about possible configurations of these central sets.
standard math Subtree core of a tree consists of either a single vertex or two adjacent vertices.
Cited as Proposition 1.3 from [12]; used in the proofs of Theorems 3.4 and 3.11.
standard math The function f_T is strictly concave: 2f_T(v) - f_T(u) - f_T(w) > 0 for adjacent u,v,w.
Cited as Lemma 1.4 from [12]; used to derive Lemma 2.6 relating subtree core to edge cuts.
standard math Among rooted binary trees on n vertices, T^n_rg maximizes the number of root-containing subtrees.
Cited as Proposition 2.11 from [11]; used in Theorems 3.4 and 3.11 when replacing a component by an rgood tree.
standard math The solution to the recurrence A_h = (A_{h-1}+1)^2 is A_h = floor(k^{2^h}) - 1 with k constant.
Cited from [2]; used only to express the subtree count of complete rgood trees and is not load-bearing for the main conjecture.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A conjecture on different central parts of binary trees." pith.science (2026). https://pith.science/paper/TVAQM62Y

@misc{pith2026200912066,
  author       = {Pith},
  title        = {Pith review of: A conjecture on different central parts of binary trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TVAQM62Y}},
  note         = {Machine review of arXiv:2009.12066}
}

abstract

Let $\Omega_n$ be the family of binary trees on $n$ vertices obtained by identifying the root of an rgood binary tree with a vertex of maximum eccentricity of a binary caterpillar. In the paper titled "On different middle parts of a tree (The electronic journal of combinatorics, 25 (2018), no. 3, paper 3.17, 32 pp)", Smith et al. conjectured that among all binary trees on $n$ vertices the pairwise distance between any two of center, centroid and subtree core is maximized by some member of the family $\Omega_n$. We first obtain the rooted binary tree which minimizes the number of root containing subtrees and then prove this conjecture. We also obtain the binary trees which maximize these distances.

Figures

Figures reproduced from arXiv: 2009.12066 by the authors.

**Figure 1.** The crg tree T 18,11 rg We lable the vertices of a longest path of the caterpillar part of T n,l rg by 1, 2, . . . , n−l+3 2 = v, where v is the root of the rgood part of it. We denote by Ωn the class of all crg trees on n vertices. Any binary tree on n ≤ 8 is isomorphic to a binary caterpillar. Due to the symmetry in the binary caterpillar trees, we observe the following: The center, centroid and subtree core coinc… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Abrew, E

N. Abrew, E. Fritscher, C. Justel and S. Kirkland, On the c haracteristic set, centroid and center for a tree, Linear and Multilinear Algebra, 65 (2017) , no. 10, 2046 - 2063

work page 2017
[2]

A. V. Aho and N. J. A. Sloane, Some doubly exponential sequ ences, Fibonacci Quart., 11 (1973), no. 4, 429 - 437

work page 1973
[3]

D. N. S. Desai and K. L. Patra, Maximizing distance betwee n center, centroid and subtree core of trees, Proc. Indian Acad. Sci. Math. Sci., 129 (2019) , no. 1, paper 7, 18 pp

work page 2019
[4]

A. J. Goldman, Optimal center location in simple network s, Transportaton Sci., 5 (1971), 212 - 221

work page 1971
[5]

Harary, Graph Theory, Addison-Wesley Publishing Co, 1969

F. Harary, Graph Theory, Addison-Wesley Publishing Co, 1969

work page 1969
[6]

Jordan, Sur les assemblages de lignes, J

C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math., 190 (1869), 70:185

work page
[7]

Kang and D

A. Kang and D. Ault, Some properties of a centroid of a free tree, Information Processing Lett., 4 (1975), 18 - 20

work page 1975
[8]

Merris, Characteristic vertices of trees, Linear and Multilinear Algebra, 22 (1987), 115 - 131

R. Merris, Characteristic vertices of trees, Linear and Multilinear Algebra, 22 (1987), 115 - 131

work page 1987

Show all 15 references

[9]

S. L. Mitchel, Another characterization of the centroid of a tree, Discrete Math., 24 (1978), 277 - 280

1978
[10]

K. L. Patra, Maximizing the distance between center, ce ntroid and characteristic set of a tree, Linear Multilinear Algebra, 55 (2007), no. 4, 381 - 397

2007
[11]

Smith, L

H. Smith, L. Sz´ ekely, H. Wang and S. Yuan, On diﬀerent mid dle parts of a tree, The electronic journal of combinatorics, 25 (2018), no. 3, pape r 3.17, 32 pp

2018
[12]

L. A. Sz´ ekely and H. Wang , On subtrees of trees, Adv. App l. Math., 34 (2005), 138 - 155

2005
[13]

Zelinka, Median and Peripherian of trees, Arch

B. Zelinka, Median and Peripherian of trees, Arch. Math ., 4 (1968), 87 - 95. Addresses:

1968
[14]

School of Mathematical Sciences, National Institute of Science Education and Research (NISE R), Bhubaneswar, P.O.- Jatni, District- Khurda, Odisha - 752050, India
[15]

Homi Bhabha National Institute (HBNI), Training School Complex, Anushakti Nagar, Mumbai - 400094, India E-mails: dinesh.pandey@niser.ac.in, klpatra@niser.ac. in 14

Pith tools

Reviewed August 27, 2026 · model on record in the stance chip above.

[1] [1]

Abrew, E

N. Abrew, E. Fritscher, C. Justel and S. Kirkland, On the c haracteristic set, centroid and center for a tree, Linear and Multilinear Algebra, 65 (2017) , no. 10, 2046 - 2063

work page 2017

[2] [2]

A. V. Aho and N. J. A. Sloane, Some doubly exponential sequ ences, Fibonacci Quart., 11 (1973), no. 4, 429 - 437

work page 1973

[3] [3]

D. N. S. Desai and K. L. Patra, Maximizing distance betwee n center, centroid and subtree core of trees, Proc. Indian Acad. Sci. Math. Sci., 129 (2019) , no. 1, paper 7, 18 pp

work page 2019

[4] [4]

A. J. Goldman, Optimal center location in simple network s, Transportaton Sci., 5 (1971), 212 - 221

work page 1971

[5] [5]

Harary, Graph Theory, Addison-Wesley Publishing Co, 1969

F. Harary, Graph Theory, Addison-Wesley Publishing Co, 1969

work page 1969

[6] [6]

Jordan, Sur les assemblages de lignes, J

C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math., 190 (1869), 70:185

work page

[7] [7]

Kang and D

A. Kang and D. Ault, Some properties of a centroid of a free tree, Information Processing Lett., 4 (1975), 18 - 20

work page 1975

[8] [8]

Merris, Characteristic vertices of trees, Linear and Multilinear Algebra, 22 (1987), 115 - 131

R. Merris, Characteristic vertices of trees, Linear and Multilinear Algebra, 22 (1987), 115 - 131

work page 1987