Automorphism Group Of Star-path Graphs And Extended-star Graphs

Cayley graphs are an important class of vertex transitive graphs and every vertex transitive graph can be viewed as a retract of a Cayley graph [4]. In this thesis, we consider some special Cayley graphs for the symmetric group. Let S_n = Sym(n) be the symmetric group on set {1,2,…, n} and T be a set of transpositions of Sym(n). The Cayley graph X(S_n, T) is connected if and only if T is a generating set for S_n. The transposition graph of T is a graph T with vertex set {1,2,… ,n} and two vertices i and j are adjacent in T if and only if (i j) ∈ T. It is known that a set of transpositions T is a minimal generating set of S_n if and only if its transposition graph is a tree [1]. SetT₃ = {(1 i), (j j + 1)|2 ≤ i ≤ m, m ≤ j ≤ n - 1} (4 ≤ m ≤ n - 1),T₄ = {(1 2i), (2i 2i + 1)|1 ≤ i ≤ m} (m ≥ 3).We denote the Cayley graph X(S_n,T₃) and X(S_2m+1,T₄) by star-path graph SP_n(m) and extended-star graph EST_2m+1 respectively. Since the transposition graphs of T₃ and T₄ are trees, then T₃ generates S_n and T₄ generates S_2m+1, star-path graph SP_n(m) and extended-star graph EST_2m+1 are connected.For a graph X, the automorphism group of X is denoted as Aut(X). In general, it is difficult to determine the automorphism group of a graph, even for Cayley graphs. In [8], the authors have determined the full automorphism group of star graph and bubble-sort graph. Inspired by those results, we intend to determine the full automorphism group of star-path graph SP_n(m) and extended-star graph EST_2m+1. Some other properties of them are also considered in this thesis. The followings are our main results:1. Aut(SP_n(m))(?)S_m-22. Aut(EST_2m+1) (?) S_m · S_2m+13. The star-path graph and the extended-star graph are not distance regular and hence not distance transitive.