Extremal Values of Ratios: Distance Problems vs. Subtree Problems in Trees

László A. Székely, Hua Wang

Research output: Contribution to journalArticlepeer-review

11 Scopus citations
4 Downloads (Pure)

Abstract

The authors discovered a dual behaviour of two tree indices, the Wiener index and the number of subtrees, for a number of extremal problems [Discrete Appl. Math. 155 (3) 2006, 374-385; Adv. Appl. Math. 34 (2005), 138-155]. Barefoot, Entringer and Székely [Discrete Appl. Math. 80(1997), 37-56] determined extremal values of σT(w)/σT(u), σT (w)/σT (v), σ(T)/σT(v), and σ(T)/σT (w), where T is a tree on n vertices, v is in the centroid of the tree T, and u,w are leaves in T. In this paper we test how far the negative correlation between distances and subtrees go if we look for the extremal values of FT (w)/FT (u), FT (w)/FT (v), F(T)/FT (v), and F(T)/FT (w), where T is a tree on n vertices, v is in the subtree core of the tree T, and u, w are leaves in T-the complete analogue, changing distances to the number of subtrees. We include a number of open problems, shifting the interest towards the number of subtrees in graphs.

Original languageAmerican English
JournalElectronic Journal of Combinatorics
Volume20
StatePublished - Jan 1 2013

Disciplines

  • Education
  • Mathematics

Keywords

  • Binary tree
  • Caterpillar
  • Center
  • Centroid
  • Distances in trees
  • Extremal problems
  • Good binary tree
  • Star tree
  • Subtree core
  • Subtrees of trees
  • Tree
  • Wiener index

Fingerprint

Dive into the research topics of 'Extremal Values of Ratios: Distance Problems vs. Subtree Problems in Trees'. Together they form a unique fingerprint.

Cite this