The Minimal Number of Subtrees of a Tree

详细信息    查看全文

• 作者：Andrew V. Sills (1)
  Hua Wang (1)
  
  1. Department of Mathematical Sciences ; Georgia Southern University ; Statesboro ; GA ; 30460 ; USA
  
• 关键词：Tree ; Subtrees ; Degree sequence ; Caterpillar ; 05C85 ; 05C05 ; 05C07
• 刊名：Graphs and Combinatorics
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：31
• 期：1
• 页码：255-264
• 全文大小：228 KB
• 参考文献：1. 脟ela E., Schmuck N.S., Wimer S., Woeginger G.J.: The Wiener maximum quadratic assignment problem. Discret. Optim. 8, 411鈥?16 (2011) CrossRef
  2. Dobrynin A., Entringer R., Gutman I.: Wiener index of trees: theory and applications. Acta Appl. Math 66, 211鈥?49 (2001) CrossRef
  3. Fischermann M., Hoffmann A., Rautenbach D., Sz茅kely L., Volkmann L.: Wiener index versus maximum degree in trees. Discret. Appl. Math 122, 127鈥?37 (2002) CrossRef
  4. Gutman I.: A property of the Wiener number and its modifications. Indian J. Chem. Sec. A 36, 128鈥?32 (1997)
  5. Heuberger C., Prodinger H.: On 伪-greedy expansions of numbers. Adv. Appl. Math 38(4), 505鈥?25 (2007) CrossRef
  6. Knudsen, B.: Optimal multiple parsimony alignment with affine gap cost using a phylogenetic tree. Lecture Notes in Bioinformatics, vol. 2812, pp. 433鈥?46. Springer, Berlin (2003)
  7. Li, S., Wang, S.: Further analysis on the total number of subtrees of trees, arXiv:1204.6152 (2012)
  8. Li, S., Wang, S.: Enumerating the total number of subtrees of trees, arXiv:1206.2975 (2012)
  9. Sills A., Wang H.: On the maximal Wiener index and related questions. Discret. Appl. Math 160, 1615鈥?623 (2012) CrossRef
  10. Szekely L.A., Wang H.: On subtrees of trees. Adv. Appl. Math. 34, 138鈥?55 (2005) CrossRef
  11. Wagner S.: Correlation of graph-theoretical indices. SIAM J. Discret. Math. 21(1), 33鈥?6 (2007) CrossRef
  12. Wang, H.: The extremal values of the Wiener index of a tree with given degree sequence. Discret. Appl. Math. 156 (2008)(14), 2647鈥?654 (Corrigendum, Discrete Appl. Math. 157(18), 3754 (2009))
  13. Wiener H.: Structural determination of paraffin boiling point. J. Am. Chem. Soc 69, 17鈥?0 (1947) CrossRef
  14. Zhang X.-D., Xiang Q.-Y., Xu L.-Q., Pan R.-Y.: The Wiener index of trees with given degree sequences. MATCH Commun. Math. Comput. Chem 60, 623鈥?44 (2008)
  15. Zhang X.-D., Liu Y., Han M.-X.: Maximum wiener index of trees with given degree sequence. MATCH Commun. Math. Comput. Chem. 64, 661鈥?82 (2010)
  16. Zhang, X.-M., Zhang, X.-D.: Minimal number of subtrees with a given degree sequence. Graphs Comb. (2013) (to appear)
  17. Zhang, X.-M., Zhang, X.-D., Gray, D., Wang, H.: The number of subtrees of trees with given degree sequence. J. Graph Theory (2012). doi:10.1002/jgt.21674
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

In this note, we consider the trees (caterpillars) that minimize the number of subtrees among trees with a given degree sequence. This is a question naturally related to the extremal structures of some distance based graph invariants. We first confirm the expected fact that the number of subtrees is minimized by some caterpillar. As with other graph invariants, the specific optimal caterpillar is nearly impossible to characterize and depends on the degree sequence. We provide some simple properties of such caterpillars as well as observations that will help finding the optimal caterpillar.