pith. sign in

arxiv: 2411.19188 · v5 · submitted 2024-11-28 · 🧮 math.CO

Characterization of Trees with Maximum Security

Alex S. A. Alochukwu , Audace A. V. Dossou-Olory , Fadekemi J. Osaye , Valisoa R. M. Rakotonarivo , Shashank Ravichandran , Sarah J. Selkirk , Hua Wang , Hays Whitlatch This is my paper

Pith reviewed 2026-05-23 08:31 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C05
keywords binary treessecurityrankprotection numberleaf-heighttree classificationextremal graph theory
0
0 comments X

The pith

Families of binary trees that maximize the sum of vertex ranks are fully classified.

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

The paper classifies the families of binary trees that achieve the highest possible security, defined as the sum of ranks over all vertices in the tree. A vertex rank equals the minimum distance from that vertex to any of its descendant leaves. A reader would care because the classification identifies exactly which rooted binary tree shapes attain the global maximum under this cumulative protection measure. The work further supplies extremal bounds on the single largest rank that can appear inside those families. The result therefore gives a complete structural description of the trees that maximize the metric.

Core claim

We produce a classification of families of binary trees for which the security is maximized. Security is the sum of the ranks of all vertices, and the rank of a vertex is the minimum distance to any of its leaf descendants. Extremal results relating to the maximum rank among all vertices in families of trees are also discussed.

What carries the argument

Security of a rooted binary tree, the sum of vertex ranks where each rank is the minimum distance from the vertex to a descendant leaf.

Load-bearing premise

That summing the minimum leaf distances over every vertex produces the correct notion of maximum security for binary trees.

What would settle it

Exhibit one binary tree whose total rank sum exceeds the value attained by every tree in the classified families.

Figures

Figures reproduced from arXiv: 2411.19188 by Alex S. A. Alochukwu, Audace A. V. Dossou-Olory, Fadekemi J. Osaye, Hays Whitlatch, Hua Wang, Sarah J. Selkirk, Shashank Ravichandran, Valisoa R. M. Rakotonarivo.

Figure 1
Figure 1. Figure 1: A binary tree with the protection number of each vertex marked on the vertex. Studies on the protection number of the root of a tree in specific families of trees as well as the general context of simply generated trees were completed in [9, 10, 11]. Most recently, extremal parameters such as the maximum protection number of a tree have been studied using powerful probabilistic and analytic techniques [5, … view at source ↗
Figure 2
Figure 2. Figure 2: All four non-isomorphic proper binary trees which achieve the maximum total rank of 8 among all proper binary trees with 7 leaves. Let L := (n1, n2, . . . , nk) correspond to the binary power representation of ℓ = X k i=1 2 ni with n1 > n2 > · · · > nk ≥ 0. We will show that TL, defined below, is a tree for which the value of R(T) is maximized. Intuitively, TL is the binary caterpillar tree on k leaves u1,… view at source ↗
Figure 3
Figure 3. Figure 3: A proper binary tree TL on ℓ = 11 leaves that maximizes R(T). The proof of this theorem will depend on several other results which will be proved throughout the remainder of this section. 2.1. Partition of a proper binary tree. Before we can prove the optimality of TL, we first introduce a “partition” of any given proper binary tree on ℓ leaves that would allow us to compare them. Definition 5. Given a pro… view at source ↗
Figure 4
Figure 4. Figure 4: Two different proper binary trees corresponding to M = (2, 2, 1, 0) with security 15 and 14, respectively. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The trees T (on the left) and T ∗ (on the right) from Lemma 6. Proof. We consider three cases depending on the ranks of the vertices u, w, u1, w1. • If RT (u1) ≤ RT (w1) ≤ RT (u) = RT (w), then RT (u0) = 1 + RT (u1) = RT ∗ (u0) and RT (w0) = 1 + RT (w1) ≤ 1 + RT (w) = RT ∗ (w0). • If RT (u1) ≤ RT (u) = RT (w) ≤ RT (w1), then RT (u0) = 1 + RT (u1) = RT ∗ (u0) and RT (w0) = 1 + RT (w) = RT ∗ (w0). • If RT (u… view at source ↗
Figure 6
Figure 6. Figure 6: The trees T (on the left) and T ∗ (on the right) from Lemma 7. Proof. As was done in the proof of Lemma 6, note that RT (w0) = 1 + RT (w) = RT ∗ (w0), and since RT (w1) ≥ RT (u) and RT ∗ (u1) = RT (u1), we obtain RT ∗ (u0) = min{1 + RT (w1), 1 + RT ∗ (u1)} ≥ min{1 + RT (u), 1 + RT ∗ (u1)} = min{1 + RT (u), 1 + RT (u1)} = RT (u0). Since the ranks of all other vertices stay the same or increase from T to T ∗… view at source ↗
Figure 7
Figure 7. Figure 7: The tree T with root vt , with u0 an ancestor of w0 from Lemma 8. Proof 1: Let v ′ 1 be the sibling of u0. By RT (v1) = min{1 + RT (v ′ 1 ), 1 + RT (u0)} and RT ∗ (v1) = min{1 + RT (v ′ 1 ), 1 + RT ∗ (u0)}, the assumption RT ∗ (v1) < RT (v1) implies that RT ∗ (u0) < RT (u0). Claim 2: RT (u1) ≤ RT ∗ (u1). Proof 2: Since T ∗ is obtained from T by “exchanging” the subtrees T(u) and T(w1), the assumptions RT (… view at source ↗
Figure 8
Figure 8. Figure 8: The tree T on the left, and the tree it generates, T ∗ , on the right from Lemma 9. These lemmata can be summarized as follows: • Lemma 6: : For pairs of saturated vertices of equal rank with neither parent of one vertex being an ancestor of the other vertex, the vertex whose sibling has a lower (or equal) rank can be swapped with the sibling of higher rank without decreasing the security of the tree. • Le… view at source ↗
Figure 9
Figure 9. Figure 9: The trees T1 (on the left) and T ∗ 1 (on the right). Following similar arguments as before and making use of the fact that u has the smallest rank among all saturated vertices, one can see that R(T ∗ 1 ) ≥ R(T1). In this case, u becomes a child of the root of T ∗ . Now consider the case where u0 is the root of T1. As long as k > 2, we may apply a similar operation to w, the saturated vertex with 2 nk−1 lea… view at source ↗
Figure 10
Figure 10. Figure 10: The tree T ∗∗ 1 . Repeatedly applying the above operation, we may insert the saturated vertices in the “correct” order to reach the tree TL. Since any partition M of a proper binary tree T can have the security (weakly) increased to the binary power representation L, and any tree with partition L can have security (weakly) increased to the tree TL, we conclude that TL is indeed a tree which maximizes the … view at source ↗
Figure 11
Figure 11. Figure 11: The different swapping configurations described above. Therefore, this operation also does not change the sum of ranks over all vertices (security). □ Remark 13. It is easy to see that Proposition 12 provides a general construction of another family of trees with maximum security. 3. Most protected proper binary trees: Almost complete trees We now prove a property of the maximum security trees discussed i… view at source ↗
Figure 12
Figure 12. Figure 12: The tree F(ℓ) corresponding to ℓ = 7 (left) and the TL tree corresponding to the same ℓ (right). Note that the security, 8, is the same in both. Algorithm for constructing F(ℓ): Let ℓ = Pk i=1 2 ni with n1 > n2 > · · · > nk ≥ 0. Suppose n1 ≥ 1. Let di = ni−1 − ni for each 1 < i ≤ k. For any m ∈ N, let cm be a complete binary tree with 2 m leaves. If qi is the root of a cni tree, let ℓi and ri be the left … view at source ↗
Figure 13
Figure 13. Figure 13: F(ℓ) for 2 n1 + 2n2 + 2n3 leaves where n1 = n2 + d2, and n2 = n3 + d3. Proof. Note that the security of a cni tree is R(cni ) = 2ni+1 − ni − 2. To verify the rank formula, let Si be the tree at the end of step i of the algorithm for constructing F(ℓ). Then S1 is a cn1 = F(2n1 ), S2 is a F(2n1 + 2n2 ) tree, and so on. Then R(Si) = R(Si−1) + R(cni+1) − R(cni ) since at each step one removes a cni tree and r… view at source ↗
Figure 14
Figure 14. Figure 14: A rooted tree with RT (r) = 1 and RT (v) > 1. There do not seem to be any obvious characteristics of the most protected vertices in a tree. Let the set of such vertices of T be denoted by Rmax(T). It may contain only one vertex (as in [PITH_FULL_IMAGE:figures/full_fig_p017_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: A rooted proper binary caterpillar. u v [PITH_FULL_IMAGE:figures/full_fig_p017_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: A rooted tree with two most protected vertices u and v. Given the motivation for vertex ranks and “protectedness”, it is natural to find, among a class of rooted trees, the most protected vertex (among all possible tree structures) and its rank. That is, for a given class of rooted trees T we want to find RT := max T ∈T max v∈V (T) RT (v) = max T ∈T Rmax(T). 17 [PITH_FULL_IMAGE:figures/full_fig_p017_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: An example of the trees T (on the left), T ′ (on the right) and the vertices u, v, w. Note that from T to T ′ , the distance between v and any of its original leaf descendants (in T, with the exception of w, which is now not a leaf) remains the same. The distance between v and any of its new leaf descendants (in T ′ ) is greater than the distance between v and w. Hence RT′(v) ≥ RT (v). Since the rank of a… view at source ↗
Figure 18
Figure 18. Figure 18: The trees T (on the left), T ′ (on the right) and the vertices r, v, w. Thus, again we only need to consider the root ranks. For our extremal structure, Fig￾ure 19 shows a rooted complete ternary tree, defined in general as the following. Definition 20. A rooted complete k-ary tree is a proprer k-ary tree, all of whose leaves are at two consecutive levels (vertices at the same distance from the root are a… view at source ↗
Figure 19
Figure 19. Figure 19: A rooted complete ternary tree. It is well known that the rooted complete k-ary tree is the densest among k-ary trees of given order, analogous to the star among general trees. We will show that such a tree also maximizes the root rank among k-ary trees of given order. Proposition 21. For a proper k-ary tree T of order n and root r such that k > 1, RT (r) ≤ ⌊logk (n(k − 1) + 1)⌋ − 1 with equality if T is … view at source ↗
read the original abstract

The rank (also known as protection number or leaf-height) of a vertex in a rooted tree is the minimum distance between the vertex and any of its leaf descendants. We consider the sum of ranks over all vertices (known as the security) in binary trees, and produce a classification of families of binary trees for which the security is maximized. In addition, extremal results relating to maximum rank among all vertices in families of trees is discussed.

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

1 major / 0 minor

Summary. The paper defines the rank of a vertex in a rooted tree as the minimum distance to any leaf descendant and security as the sum of these ranks over all vertices. It claims to classify families of binary trees that maximize security and discusses related extremal results on the maximum rank among vertices.

Significance. A correct classification of binary trees maximizing security under a fixed size constraint would provide a concrete contribution to extremal problems on rooted trees in combinatorics. The definitions are standard and the problem is well-posed once the size parameter is fixed, but the manuscript's central claim as stated does not address this.

major comments (1)
  1. [Abstract] Abstract and Introduction: the claim that the paper produces 'a classification of families of binary trees for which the security is maximized' omits any size constraint (e.g., among all rooted binary trees on n vertices or with n leaves). Without such a constraint, security is unbounded because adding levels increases the sum of ranks; the maximality statement is therefore undefined and the classification cannot be verified.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed review and for identifying this important clarification needed in the abstract and introduction. We address the comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract and Introduction: the claim that the paper produces 'a classification of families of binary trees for which the security is maximized' omits any size constraint (e.g., among all rooted binary trees on n vertices or with n leaves). Without such a constraint, security is unbounded because adding levels increases the sum of ranks; the maximality statement is therefore undefined and the classification cannot be verified.

    Authors: We agree that the abstract and introduction must explicitly indicate the size constraint. The results classify binary trees on a fixed number n of vertices (equivalently, with a fixed number of leaves) that maximize security; without this the statement is indeed ill-posed. We will revise the abstract to: 'We consider the sum of ranks over all vertices (known as the security) in binary trees with n vertices, and produce a classification of families of binary trees for which the security is maximized.' Parallel wording will be added to the introduction and the statement of the main theorem. This makes the claim precise and verifiable. revision: yes

Circularity Check

0 steps flagged

No circularity detected; classification claim is a standard extremal result on explicitly defined parameters.

full rationale

The provided abstract and description contain only definitions of rank (min distance to leaf descendant) and security (sum of ranks), followed by a claim to classify families maximizing security in binary trees. No equations, derivations, fitted parameters, or self-citations appear that could reduce a result to its inputs by construction. The extremal problem is well-posed under the standard interpretation of fixed n (vertices or leaves), making the derivation self-contained against external combinatorial benchmarks with no load-bearing self-reference or renaming of known patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so no free parameters, additional axioms, or invented entities can be identified from the paper itself.

axioms (1)
  • domain assumption Rank of a vertex equals the minimum distance to any leaf descendant.
    This definition is used to define security as the sum of ranks.

pith-pipeline@v0.9.0 · 5636 in / 1043 out tokens · 95329 ms · 2026-05-23T08:31:29.252539+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

18 extracted references · 18 canonical work pages

  1. [1]

    Mikl´ os B´ ona.k-protected vertices in binary search trees.Adv. in Appl. Math., 53:1–11, 2014

    work page 2014

  2. [2]

    On a random search tree: asymptotic enumeration of vertices by distance from leaves—corrigendum.Adv

    Mikl´ os B´ ona and Boris Pittel. On a random search tree: asymptotic enumeration of vertices by distance from leaves—corrigendum.Adv. in Appl. Probab., 54(2):337–339, 2022

    work page 2022

  3. [3]

    Gi-Sang Cheon and Louis W. Shapiro. Protected points in ordered trees.Appl. Math. Lett., 21(5):516– 520, 2008

    work page 2008

  4. [4]

    Keith Copenhaver.k-protected vertices in unlabeled rooted plane trees.Graphs Combin., 33(2):347– 355, 2017

    work page 2017

  5. [5]

    Goh, and Rosie Y

    Luc Devroye, Marcel K. Goh, and Rosie Y. Zhao. On the peel number and the leaf-height of Galton- Watson trees.Combin. Probab. Comput., 32(1):68–90, 2023

    work page 2023

  6. [6]

    Protected nodes and fringe subtrees in some random trees.Electron

    Luc Devroye and Svante Janson. Protected nodes and fringe subtrees in some random trees.Electron. Commun. Probab., 19:no. 6, 10, 2014

    work page 2014

  7. [7]

    Rosena R. X. Du and Helmut Prodinger. Notes on protected nodes in digital search trees.Appl. Math. Lett., 25(6):1025–1028, 2012

    work page 2012

  8. [8]

    Jeffrey Gaither, Yushi Homma, Mark Sellke, and Mark D. Ward. On the number of 2-protected nodes in tries and suffix trees. In Nicolas Broutin and Luc Devroye, editors,23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA’12), pages 381–398, Montreal, Canada, 2012. Discrete Mathematics and Th...

    work page 2012

  9. [9]

    Protec- tion numbers in simply generated trees and P´ olya trees.Appl

    Bernhard Gittenberger, Zbigniew Go le˛biewski, Isabella Larcher, and Ma lgorzata Sulkowska. Protec- tion numbers in simply generated trees and P´ olya trees.Appl. Anal. Discrete Math., 17:1–24, 2023

    work page 2023

  10. [10]

    Protection number of recursive trees

    Zbigniew Go le˛biewski and Mateusz Klimczak. Protection number of recursive trees. InProceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pages 45–53, Philadelphia PA, 2019. SIAM

    work page 2019

  11. [11]

    Protection number in plane trees.Appl

    Clemens Heuberger and Helmut Prodinger. Protection number in plane trees.Appl. Anal. Discrete Math., 11:314–326, 2017

    work page 2017

  12. [12]

    Selkirk, and Stephan Wagner

    Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner. The distribution of the maximum pro- tection number in simply generated trees. arXiv preprint arXiv:2305.09427

    work page arXiv

  13. [13]

    CeciliaHolmgrenandSvanteJanson.Asymptoticdistributionoftwo-protectednodesinternarysearch trees.Electron. J. Probab., 20:1–20, 2015. 22

    work page 2015

  14. [14]

    Limit laws for functions of fringe trees for binary search trees and random recursive trees.Electron

    Cecilia Holmgren and Svante Janson. Limit laws for functions of fringe trees for binary search trees and random recursive trees.Electron. J. Probab., 20:no. 4, 51, 2015

    work page 2015

  15. [15]

    Mahmoud and Mark D

    Hosam M. Mahmoud and Mark D. Ward. Asymptotic properties of protected nodes in random recur- sive trees.J. Appl. Probab., 52(1):290–297, 2015

    work page 2015

  16. [16]

    Mahmoud and Mark Daniel Ward

    Hosam M. Mahmoud and Mark Daniel Ward. Asymptotic distribution of two-protected nodes in random binary search trees.Appl. Math. Lett., 25(12):2218–2222, 2012

    work page 2012

  17. [17]

    Protected points ink-ary trees.Appl

    Toufik Mansour. Protected points ink-ary trees.Appl. Math. Lett., 24(4):478–480, 2011

    work page 2011

  18. [18]

    On subtrees of trees.Advances in Applied Mathematics, 34(1):138–155, 2005

    Laszlo Szekely and Hua Wang. On subtrees of trees.Advances in Applied Mathematics, 34(1):138–155, 2005. (Alex S. A. Alochukwu)Albany State University, United States of America. Email address:alex.alochukwu (at) asurams.edu (AudaceA.V.Dossou-Olory)InstitutNationaldel’Eau, andCentred’Excellenced’Afrique pour l’Eau et l’Assainissement and Institut de Math´em...

    work page 2005