Some results about the inset edge and average distance of trees

DOI10.1016/J.DAM.2022.09.023zbMATH Open1505.05042arXiv2008.05677OpenAlexW4309029941MaRDI QIDQ2104937FDOQ2104937

Authors: M. H. Khalifeh, Abdol-Hossein Esfahanian 

Publication date: 8 December 2022

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

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.

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

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

zbMATH Keywords

treeunicyclic graphsWiener indexaverage distanceinset edge

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• Title not available (Why is that?)

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)