Abstract
The study of extremal problems on various graph invariants has received great attention in recent years. Among the most well known graph invariants is the sum of distances between all pairs of vertices in a graph. This is also known as the Wiener index for its applications in Chemical Graph Theory. Many interesting properties related to this concept have been established for extremal trees that maximize or minimize it. Recently a vertex-weighted analogue of sum of distances is introduced for vertex weighted trees. Some extremal results on (vertex-weighted) trees were obtained, by Goubko, for trees with a given degree sequence. In this note we first analyze the behavior of vertex-weighted distance sum in general, identifying the “middle part” of a tree analogous to that with respect to the regular distance sum. We then provide a simpler approach (than that of Goubko's) to obtain a stronger result regarding the extremal tree with a given degree sequence. Questions and directions for potential future study are also discussed.
Original language | English |
---|---|
Pages (from-to) | 435-442 |
Number of pages | 8 |
Journal | Applied Mathematics and Computation |
Volume | 333 |
DOIs | |
State | Published - Sep 15 2018 |
Scopus Subject Areas
- Computational Mathematics
- Applied Mathematics
Keywords
- Distances
- Extremal
- Trees
- Vertex weighted