Automorphism Groups of the Augmented Distance Graphs of Trees

Sportsman, Joseph Scott

Permalink

https://hdl.handle.net/2142/71261 Copy

Description

Title

Automorphism Groups of the Augmented Distance Graphs of Trees

Author(s)

Sportsman, Joseph Scott

Issue Date

1987

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Mathematics

Abstract

• In algebraic graph theory one studies algebraic variants of graphs by forming matrices and groups relating to the graph. One example of this is the distance matrices, $\Gamma\sb{\rm i}$, and their associated groups.
• In this thesis we introduce the graphs, $\Gamma\sp{\rm (r)}$ defined by $\Gamma\sp{\rm (r)}$ = $\Gamma\sb1$ + $\Gamma\sb2$ + $\cdots$ + $\Gamma\sb{\rm r}$ and their automorphism groups G$\sp{\rm (r)}$. We show that for a tree $\Gamma$, the groups G$\sp{\rm (r)}$ form a tower which is not the case for arbitrary graphs. From this, we give a description of the structure of G$\sp{\rm (r)}$ for trees and completely characterize the trees of a fixed diameter which have minimal group tower length. Also we introduce a new parameter, $\chi$ for trees defined as follows: Let x and y be vertices of $\Gamma$. Partition the remaining vertices into three sets; W(x) = $\{$w$\epsilon$V($\Gamma$): $\partial$(w,x)$$ 0$\}$. It turns out that $\chi$ has nice properties. One theorem we prove is the following: If $\Gamma$ is a tree of diameter greater than 3, and m = min$\{\chi$ + 1, (d/2) $\}$, then G$\sp{\rm (m+1)}$ $\not=$ G, but G$\sp{\rm (r)}$ = G for all r $\leq$ m.

Graduation Semester

1987

Type of Resource

text

Permalink

http://hdl.handle.net/2142/71261

Owning Collections