Abstract
The sum of distances between all pairs of vertices (denoted by σ(⋅) and called the Wiener index) and the number of subtrees (denoted by F(⋅) and called the subtree index) of a graph G are two representative graph invariants that have been extensively studied. The “local” version of these graph invariants (i.e. sum of distances from a given vertex, called the distance of the vertex, and the number of subtrees containing such a vertex, called the local subtree index of the vertex) have been studied. The distance of a vertex v in a tree T, denoted by σ T (v), attains its minimum at one or two adjacent vertices called the centroid while the maximum σ T (v) occurs at one or more leaves. On the other hand, the local subtree index, denoted by F T (v), attains its maximum at one or two adjacent vertices called the subtree core and the minimum F T (v) occurs at one ore more leaves. In this paper we study the difference between the values of σ T (v) at a centroid vertex and a leaf, called the σ-span, and similarly the F-span for the difference in values of the local subtree index at the subtree core and at a leaf. Among trees and full binary trees (trees in which each vertex has degree 1 or 3) on a given number of vertices we study the maximum and minimum possible values of the σ-span and F-span. The extremal structures corresponding to some of these extremal values are also presented. Some unsolved problems are also discussed and proposed as open questions.
Original language | English |
---|---|
Pages (from-to) | 1564-1576 |
Number of pages | 13 |
Journal | Discrete Mathematics |
Volume | 342 |
Issue number | 6 |
DOIs | |
State | Published - Jun 2019 |
Keywords
- Distance
- Full binary tree
- Span
- Subtree
- Tree