Some extremal ratios of the distance and subtree problems in binary trees

DOI10.1016/J.AMC.2019.05.023zbMATH Open1428.05057arXiv1712.00695OpenAlexW2963963481WikidataQ127744759 ScholiaQ127744759MaRDI QIDQ2279596FDOQ2279596

Authors: Shuchao Li, Hua Wang, Shujing Wang 

Publication date: 13 December 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Abstract: Among many topological indices of trees the sum of distances $sigma(T)$ and the number of subtrees $F(T)$ have been a long standing pair of graph invariants that are well known for their negative correlation. That is, among various given classes of trees, the extremal structures maximizing one usually minimize the other, and vice versa. By introducing the "local" versions of these invariants, $sigm{a}_T(v)$ for the sum of distance from $v$ to all other vertices and $F_T(v)$ for the number of subtrees containing $v$, extremal problems can be raised and studied for vertices within a tree. This leads to the concept of "middle parts" of a tree with respect to different indices. A challenging problem is to find extremal values of the ratios between graph indices and corresponding local functions at middle parts or leaves. This problem also provides new opportunities to further verify the the correlation between different indices such as $sigma(T)$ and $F(T)$. Such extremal ratios, along with the extremal structures, were studied and compared for the distance and subtree problems for general trees In this paper this study is extended to binary trees, a class of trees with numerous practical applications in which the extremal ratio problems appear to be even more complicated. After justifying some basic properties on the distance and subtree problems in trees and binary trees, characterizations are provided for the extremal structures achieving two extremal ratios in binary trees of given order. The generalization of this work to $k$-ary trees is also briefly discussed. The findings are compared with the previous established extremal structures in general trees. Lastly some potential future work is mentioned.

Full work available at URL: https://arxiv.org/abs/1712.00695

Recommendations

• Extremal values of ratios: distance problems vs. subtree problems in trees
• Extremal values of ratios: distance problems vs. subtree problems in trees. II
• On \(\sigma\)-span and \(F\)-span of trees and full binary trees
• The distances between internal vertices and leaves of a tree
• Further analysis on the total number of subtrees of trees

zbMATH Keywords

treeWiener indexsubtreeratio

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30)

Cites Work

• Wiener index versus maximum degree in trees
• On subtrees of trees
• Superdominance order and distance of trees with bounded maximum degree
• Extremal values of ratios: distance problems vs. subtree problems in trees. II
• Largest Number of Subtrees of Trees with a Given Maximum Degree
• Wiener index of trees: Theory and applications
• Distance in graphs
• Title not available (Why is that?)
• Extremal values for ratios of distances in trees
• Extremal values of ratios: distance problems vs. subtree problems in trees
• Greedy trees, caterpillars, and Wiener-type graph invariants
• Title not available (Why is that?)
• The Number of Subtrees of Trees with Given Degree Sequence
• The Wiener maximum quadratic assignment problem
• The extremal values of the Wiener index of a tree with given degree sequence
• Binary trees with the largest number of subtrees
• Title not available (Why is that?)
• On distances in vertex-weighted trees
• Further analysis on the total number of subtrees of trees
• The Maximum Wiener Index of Trees with Given Degree Sequences
• Trees with the mos subtrees - an algorithmic approach
• Title not available (Why is that?)
• Correlation of Graph‐Theoretical Indices
• Vertex-based and edge-based centroids of graphs
• Sum of weighted distances in trees

Cited In (7)

• Enumeration of subtrees and BC-subtrees with maximum degree no more than \(k\) in trees
• On \(\sigma\)-span and \(F\)-span of trees and full binary trees
• A Ratio Inequality for Binary Trees and the Best Secretary
• Extremal problems on \(k\)-ary trees with respect to the cover cost and reverse cover cost
• On subtree number index of generalized book graphs, fan graphs, and wheel graphs
• On a problem of Yekutieli and Mandelbrot about the bifurcation ratio of binary trees
• Extremal distances for subtree transfer operations in binary trees

This page was built for publication: Some extremal ratios of the distance and subtree problems in binary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279596)