On distances in vertex-weighted trees

Qingqiong Cai, Fuyuan Cao, Tao Li, Hua Wang

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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 languageEnglish
Pages (from-to)435-442
Number of pages8
JournalApplied Mathematics and Computation
Volume333
DOIs
StatePublished - Sep 15 2018

Scopus Subject Areas

  • Computational Mathematics
  • Applied Mathematics

Keywords

  • Distances
  • Extremal
  • Trees
  • Vertex weighted

Fingerprint

Dive into the research topics of 'On distances in vertex-weighted trees'. Together they form a unique fingerprint.

Cite this