Some results about the inset edge and average distance of trees (Q2104937)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 7628647
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Some results about the inset edge and average distance of trees |
scientific article; zbMATH DE number 7628647 |
Statements
Some results about the inset edge and average distance of trees (English)
0 references
8 December 2022
0 references
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.
0 references
average distance
0 references
inset edge
0 references
Wiener index
0 references
tree
0 references
unicyclic graphs
0 references
0 references
0 references
0 references
0.8258841
0 references
0 references
