On BC-trees and BC-subtrees

Yu Yang, Deqiang Wang, Hua Wang, Hongbo LiuarXiv 2013 · arXiv

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.

Figure 3: Reorganization 1, illustrating the process of transforming a star-like structure into a tree with more internal nodes.
Figure 5: Reorganization 2, showing a subsequent step in the algorithmic construction of complex BC-trees.

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

BibTeX
@misc{yang2013bc,
  author = {Yu Yang and Deqiang Wang and Hua Wang and Hongbo Liu},
  title = {{On BC-trees and BC-subtrees}},
  year = {2013},
  eprint = {1305.4711},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1305.4711},
}
Figure