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

DOI10.1016/J.AMC.2019.05.023zbMATH Open1428.05057OpenAlexW2963963481WikidataQ127744759 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

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

Cited In (9)

• 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
• Extremal values of ratios: distance problems vs. subtree problems in trees. II
• Extremal values of ratios: distance problems vs. subtree problems in trees
• 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)