Login | Register

On strongly regular graphs

Title:

On strongly regular graphs

Behbahani, Majid (2009) On strongly regular graphs. PhD thesis, Concordia University.

[img]
Preview
Text (application/pdf)
NR63369.pdf - Accepted Version
2MB

Abstract

Strongly regular graphs are regular graphs with the additional property that the number of common neighbours for two vertices depends only on whether the vertices are adjacent or non-adjacent. From an algebraic point of view, a graph is strongly regular if its adjacency matrix has exactly three eigenvalues. Strongly regular graphs have very interesting algebraic properties due to their strong regularity conditions. Many strongly regular graphs are known to have large and interesting automorphism groups [23]. In [23] it is also conjectured that almost all strongly regular graphs are asymmetric. Peter Cameron in [7] mentions that "Strongly regular graphs lie on the cusp between highly structured and unstructured." Although strongly regular graphs have been studied extensively since they were introduced, there is very little known about the automorphism group of an arbitrary strongly regular graph based on its parameters. In this thesis, we have developed theory for studying the automorphisms of strongly regular graphs. Our study is both mathematical and computational. On the computational side, we introduce the notion of orbit matrices. Using these matrices, we were able to show that some strongly regular graphs do not admit an automorphism of a certain order. Given the size of the automorphism, we can generate all of the orbit matrices, using a computer program. Another computer program is implemented that generates all the strongly regular graphs from that orbit matrix. From a mathematical point of view, we have found an upper bound on the number of fixed points of the automorphisms of a strongly regular graph. This upper bound is a new upper bound and is obtained by algebraic techniques

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Behbahani, Majid
Pagination:xii, 121 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Date:2009
Thesis Supervisor(s):Lam, C
ID Code:976720
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:31
Last Modified:18 Jan 2018 17:43
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top