Introduction
In graph theory, a tree is its own core when it is a BC-tree (or block-cutpoint-tree). These structures are defined by a strict parity constraint: the distance between any two leaves must be even. This paper explores the structural properties of BC-trees, providing constructive algorithms for their generation and identifying extremal results regarding the number of BC-subtrees they contain.
Constructive Algorithms for BC-trees
The authors present two primary algorithms to generate BC-trees of a specific order $p$ and leaf count $r$. These algorithms typically start with a star graph ($K_{1,n-1}$) and use a "reorganization" process—moving edges to transform leaves into internal nodes—until the desired configuration is reached while maintaining the even-distance property.
These reorganizations allow for the systematic exploration of tree topologies. A key finding from these constructions is that a BC-tree cannot have exactly two internal vertices, as the distance between leaves on different internal nodes would be 3, violating the core definition.
Extremal Results: Stars vs. Paths
The paper establishes quantitative bounds for the number of BC-subtrees, $\eta_{BC}(T)$. Similar to general trees, the star graph ($K_{1,n-1}$) is the maximal structure, containing $2^{n-1} - n$ BC-subtrees. Conversely, the path graph ($P_n$) is the minimal structure, with approximately $n^2/4$ BC-subtrees.
Furthermore, the existence of an $r$-leaf BC-tree of order $p$ is constrained by parity. For instance, for even $p$, such a tree exists if and only if $3 \leq r \leq p-1$ and $r \neq p-2$.
The BC-Subtree-Core
The "middle" of a BC-tree, or the BC-subtree-core (the set of vertices appearing in the most BC-subtrees), behaves differently than in standard trees. While the traditional subtree-core consists of one or two adjacent vertices, the BC-subtree-core can be non-adjacent and may not overlap with the tree's traditional center or centroid. This "chaotic" behavior is a direct result of the parity constraints imposed on BC-subtrees.
Conclusion
This work fills a gap in the understanding of parity-constrained tree structures. While the paper provides existence theorems and extremal bounds, the strange behavior of the BC-subtree-core remains an area for future research. Specifically, questions persist regarding the maximum distance between core vertices and the relationship between different types of tree centers.
Summary updated