Thumbnail Image
Publication

Automorphism Groups of k-star n-path Saturated Graphs

Li, Shushangxuan
Citations
Altmetric:
Contributor
Photographer
Author
Li, Shushangxuan
Artist
Editor
Advisor
Keywords
Text, Honors papers, Mathematics and Computer Science, Department of
Local ID
Collections
Honors Papers
Show all metadata
Files
Thumbnail Image
Sandra Li's Honors Thesis.pdf
Adobe PDF, 35.71 MB
URI
http://hdl.handle.net/10267/33680
Abstract
In combinatorics, graph theory and Ramsey theory are two rich subjects of study. There are many directions and problems to pursue. The automorphism groups of graphs provide a connection between graph theory and group theory. In this project, we will study a Ramsey-theoretic aspect of graph theory. The main question is: how many edges must a tree contain in order to guarantee the presence of a k-star or an n-path? Another way to think about this problem is: what is the maximum number of edges that a tree with no k-star or n-path contain? We will establish a general formula for the number of edges using induction and classify the trees that achieve this maximum. In addition, we will describe the automorphism group of these saturated trees. The same questions will be studied for connected graphs following a similar procedure. We will show that the number of edges for connected graphs has a close relation with the one for trees.
Description