Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/43526
Title: CAYLEY GRAPHS AND APPLICATIONS OF POWER SUM SYMMETRIC FUNCTION
Authors: TERRY LAU SHUE CHIEN
Keywords: Cayley Graph, Graph Theory, Symmetric Functions, Independent Set
Issue Date: 10-Jun-2013
Source: TERRY LAU SHUE CHIEN (2013-06-10). CAYLEY GRAPHS AND APPLICATIONS OF POWER SUM SYMMETRIC FUNCTION. ScholarBank@NUS Repository.
Abstract: We consider the Cayley graph on the symmetric group Sn generated by di fferent generating sets and we are interested in finding eigenvalues of the graph. With the eigenvalues, we are able to bound its largest independent set by using Delsarte-Ho man Bound. It is well known that the eigenvalues of this graph are indexed by partitions of n. We study the formula developed by Renteln and Ku and Wong to determine the eigenvalues of this graph. By investigating property of power sum symmetric function, we derive some new Cayley graphs and determine their eigenvalues so that we can bound the largest independent set. With manipulations of different choice of power sum symmetric function, we are able to produce new graphs and calculate their eigenvalues. We also look at some subgraphs of derangement graph and generalize properties in derangement graph into these subgraphs by analysis of order of eigenvalues.
URI: http://scholarbank.nus.edu.sg/handle/10635/43526
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
A0038178X_MSc.pdf729.04 kBAdobe PDF

OPEN

NoneView/Download

Page view(s)

189
checked on Dec 11, 2017

Download(s)

46
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.