Central and Bicentral Trees

Central and Bicentral Trees

Definition: If a graph $G$ is a tree, then $G$ is said to be Central if the deletion of all leaves in $G$ results in a subgraph $G_1$ and the deletion of all of the leaves in $G_1$ results in a subgraph $G_2$, …, and the deletion of all leaves in $G_n$ results in a single vertex. If the deletion of leaves in $G_n$ results in two vertices, then $G$ is said to be a Bicentral tree.

For example, the following exhibits two trees, one of which is central and one of which is bicentral:

Screen%20Shot%202014-03-20%20at%201.32.22%20AM.png

You should be able to imagine that the deletion of the leaves results in $1$ vertex for the first graph and $2$ vertices for the second graph. Leaves can be continually deleted until it is evident that a graph is either central or bicentral.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License