On σ-span and F-span of trees and full binary trees

Shuchao Li, Hua Wang, Shujing Wang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish
Pages (from-to)1564-1576
Number of pages13
JournalDiscrete Mathematics
Volume342
Issue number6
DOIs
StatePublished - Jun 2019

Keywords

  • Distance
  • Full binary tree
  • Span
  • Subtree
  • Tree

Fingerprint

Dive into the research topics of 'On σ-span and F-span of trees and full binary trees'. Together they form a unique fingerprint.

Cite this