Skip to main content
Article
Enumeration of BC-Subtrees of trees
Theoretical Computer Science
  • Yu Yang, Dalian Maritime University
  • Hongbo Liu, Dalian Maritime University
  • Hua Wang, Georgia Southern University
  • Scott Makeig, University of California San Diego
Document Type
Article
Publication Date
5-17-2015
DOI
10.1016/j.tcs.2015.02.028
Disciplines
Abstract

A BC-tree (block-cutpoint-tree) is a tree (with at least two vertices) where the distance between any two leaves is even. Motivated from the study of the “core” of a graph, BC-trees form an interesting class of trees. We provide a comprehensive study of questions related to BC-trees. As the analogue of the study of extremal questions on subtrees of trees, we first characterize the general extremal trees that maximize or minimize the number of BC-subtrees or leaf-containing BC-subtrees. We further discuss the “middle part” of a tree with respect to the number of BC-subtrees, namely the BC-subtree-core that behaves in a rather different way than all previously known “middle parts” of a tree. Last but not least, fast algorithms are proposed (following similar ideas as those of the enumeration of subtrees) for enumerating various classes of BC-subtrees of a tree.

Citation Information
Yu Yang, Hongbo Liu, Hua Wang and Scott Makeig. "Enumeration of BC-Subtrees of trees" Theoretical Computer Science Vol. 580 (2015) p. 59 - 74 ISSN: 0304-3975
Available at: http://works.bepress.com/hua_wang/97/