Automorphism Groups of k-star n-path Saturated Graphs

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.