Integer sequences associated with trees.
Item
-
Title
-
Integer sequences associated with trees.
-
Identifier
-
AAI9510719
-
identifier
-
9510719
-
Creator
-
Skurnick, Ronald Stuart.
-
Contributor
-
Adviser: Joseph Malkevitch
-
Date
-
1994
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Mathematics
-
Abstract
-
The weight a(v) of a vertex v of a tree T is the size (i.e., number of edges) of a maximal subtree T{dollar}\sb{lcub}\rm v{rcub}{dollar} of greatest size which starts at v in T. The centroid of T is the set of all vertices of T of minimum weight.;A non-increasing finite sequence A = {dollar}\{lcub}\rm a\sb1,\ a\sb2, \ \...,\ a\sb{lcub}\rm n{rcub}\{rcub}{dollar} (n {dollar}\geq{dollar} 2) of positive integers is said to be the centroid sequence of a tree if there exists a tree T of order n whose vertices can be labeled v{dollar}\sb1{dollar}, v{dollar}\sb2{dollar}, ..., v{dollar}\sb{lcub}\rm n{rcub}{dollar} such that a(v{dollar}\sb{lcub}\rm i{rcub}{dollar}) = a{dollar}\sb{lcub}\rm i{rcub}{dollar} for each i = 1, 2, ..., n. The centroid sequence of a tree of order n {dollar}\geq{dollar} 2 is characterized and properties of the centroid sequence of a tree are presented.;A caterpillar C is a tree on n {dollar}\geq{dollar} 3 vertices such that if all the 1-valent vertices of C are removed, the resulting graph is a (possibly degenerate) path. The centroid sequence of a caterpillar is characterized.;The eccentricity e(v) of a vertex v of a connected graph G is the maximum distance in G from v to any vertex of G. The center of G is the set of all vertices of G of minimum eccentricity. Several characterizations of the center of a tree are given.;A non-decreasing finite sequence E = {dollar}\{lcub}\rm e\sb1,\ e\sb2,\ \...,\ e\sb{lcub}n{rcub}\{rcub}{dollar} (n {dollar}\geq{dollar} 2) of positive integers is said to be the eccentricity sequence of a tree if there exists a tree T of order n whose vertices can be labeled v{dollar}\sb1{dollar}, v{dollar}\sb2{dollar}, ..., v{dollar}\sb{lcub}\rm n{rcub}{dollar} such that e(v{dollar}\sb{lcub}\rm i{rcub}{dollar}) = e{dollar}\sb{lcub}\rm i{rcub}{dollar} for each i = 1, 2, ..., n. A new proof of and results related to Lesniak's characterization of the eccentricity sequence of a tree on n {dollar}\geq{dollar} 2 vertices are presented. Additional results and algorithms concerning centers, centroids, and their associated sequences are also provided. In particular, results are obtained for when a vertex v in a graph G is in the centroid or center of some spanning tree of G, or is the centroid or center of some spanning tree of G.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
