Some results about the inset edge and average distance of trees

DOI10.1016/J.DAM.2022.09.023MaRDI QIDQ2104937zbMATH OpenOpenAlexFDO

Authors M. H. Khalifeh, Abdol-Hossein Esfahanian

Publication date 8 December 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

average distanceinset edgetreeunicyclic graphsWiener index

Mathematics Subject Classification ID

Trees (05C05) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Distance in graphs (05C12) Chemical graph theory (05C92) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Abstract: An added edge to a graph is called an inset edge. Predicting k inset edges which minimize the average distance of a graph is known to be NP-Hard. However, when k = 1 the complexity of the problem is polynomial. In this paper, some tools for a precise analysis of the problem for the trees are established. Using the tools, we can avoid using the distance matrix. This leads to more efficient algorithms and a better analysis of the problem. Several applications of the tools as well as a tight bound for the change of average distance when an inset edge is added to a tree are presented.

Review text

An added edge to a graph is called an inset edge. Predicting \(k\) inset edges, which minimize the average distance of a graph, is known to be NP-hard except when \(k = 1\), where the complexity of the problem is polynomial. This article discusses some tools for a precise analysis of the effect of inseting edges on the tree's average distance. The tools help to avoid the use of distance matrices for a better performance of algorithms. Some applications of the tools and a tight bound for the change of average distance when an inset edge is added to a tree are presented.

Recommendations

• scientific article; zbMATH DE number 431364
• On the distance distribution of trees
• Mean distance in a tree
• A distance approximating trees
• scientific article; zbMATH DE number 508964
• Average distance and maximum induced forest
• Note on the edge rotation distance between trees
• On the distance spectrum of trees
• Publication:4870414
• Note on a relation between the harmonic index and the average distance of trees

Cites work

• A class of trees and its Wiener index
• An Economic Model of Friendship: Homophily, Minorities, and Segregation
• scientific article; zbMATH DE number 2121253 (Why is no real title available?)
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• On extensions of Wiener index
• The average diameter of general tree structures
• The average distances in random graphs with given expected degrees
• Wiener number of vertex-weighted graphs and a chemical application

Cited in

(1)

• scientific article; zbMATH DE number 508964 (Why is no real title available?)

This page was built for publication: Some results about the inset edge and average distance of trees

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