Search

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. [ABSTRACT FROM AUTHOR]

Abstract: For a simple connected graph and an integer with diam(), a radio -coloring of is an assignment of non-negative integers to the vertices of such that for each pair of distinct vertices and of , where diam() is the diameter of and is the distance between and in . The span of a radio -coloring is the largest integer assigned by to a vertex of , and the radio -chromatic number of , denoted by , is the minimum of spans of all possible radio -colorings of . If , then is known as the antipodal number of . In this paper, we give an upper and a lower bound of for all possible values of , and . Also we show that these bounds are sharp for antipodal number of for several values of and . [Copyright &y& Elsevier]

Abstract: Let be the collection of sets T such that the greedy algorithm obtains the optimal T-span of for all , the collection of sets T such that is true for all graphs G. Many families in or have been discovered. We know that r-initial set and k multiple of s set are all in . Liu (T-colorings of graphs, Discrete Math. 10 (1992), 203–212) extended k multiple of s set by union with another set . In this paper, we continue to study the T-set in and , extending some T-sets by the similar way. [Copyright &y& Elsevier]