Skip to main content
Article
On Algorithms for Enumerating BC-Subtrees of Unicyclic and Edge-Disjoint Bicyclic Graphs
Discrete Applied Mathematics
  • Yu Yang, Dalian Maritime University
  • Hongbo Liu, Dalian Maritime University
  • Hua Wang, Georgia Southern University
  • Shigang Feng, Dalian Maritime University
Document Type
Article
Publication Date
4-20-2016
DOI
10.1016/j.dam.2015.09.025
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. A BC-subtree is a subtree of a connected graph that is also a BC-tree. In this paper, we first consider subtrees containing a specific vertex with conditions on the parity of the distances from this vertex to the leaves and the enumeration of such subtrees of unicyclic and edge-disjoint bicyclic graphs. Using these results and through generating functions of BC-subtrees, we present graph-theoretical based algorithms for enumerating BC-subtrees, BC-subtrees containing a given vertex, and BC-subtrees containing two distinct vertices of unicyclic and edge-disjoint bicyclic graphs. These results also provide a novel perspective on exploring the structural properties of molecules.

Citation Information
Yu Yang, Hongbo Liu, Hua Wang and Shigang Feng. "On Algorithms for Enumerating BC-Subtrees of Unicyclic and Edge-Disjoint Bicyclic Graphs" Discrete Applied Mathematics Vol. 203 (2016) p. 184 - 203 ISSN: 0166-218X
Available at: http://works.bepress.com/hua_wang/110/