Algorithms Based on Path Contraction Carrying Weights for Enumerating Subtrees of Tricyclic Graphs. (17th July 2020)

• Record Type: Journal Article
• Authors: Yang, Yu; Chen, Beifang; Zhang, Guoping; Li, Yongming; Sun, Daoqiang; Liu, Hongbo
• Is Part Of: Computer journal. Volume 65:Number 3(2022)
• Page Start: 554
• Page End: 572
• Publication Date: 2020-07-17
• Subjects: subtree number index -- generating function -- path contraction carrying weights -- structural decomposition -- tricyclic graphs; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa084
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: The subtree number index of a graph, defined as the number of subtrees, attracts much attention recently. Finding a proper algorithm to compute this index is an important but difficult problem for a general graph. Even for unicyclic and bicyclic graphs, it is not completely trivial, though it can be figured out by try and error. However, it is complicated for tricyclic graphs. This paper proposes path contraction carrying weights (PCCWs) algorithms to compute the subtree number index for the nontrivial case of bicyclic graphs and all 15 cases of tricyclic graphs, based on three techniques: PCCWs, generating function and structural decomposition. Our approach provides a foundation and useful methods to compute subtree number index for graphs with more complicated cycle structures and can be applied to investigate the novel structural property of some important nanomaterials such as the pentagonal carbon nanocone.