Matrices of graphs and designs with emphasis on their integral eigen-pair balance characteristic.
Loading...
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The interplay between graphs and designs is well researched. In this dissertation we connect
designs and graphs entirely through their associated matrices – the incidence matrix for designs
and the adjacency matrix for graphs. The properties of graphs are immediately adopted by their
associated designs, and the linear algebra of the common matrix, will apply to both designs and
graphs sharing this matrix.
We apply various techniques of finding the eigenvalues of the matrices associated with
graphs/designs, to determine the eigenvalues of well-known classes of graphs, such as complete
graphs, complete bipartite graphs, cycles, paths, wheels, stars and hypercubes.
Graphs which are well connected, or edge-balanced, in terms of a centrally defined set of
vertices, appear to give rise to a conjugate pair of eigenvalues.
The association of integers, conjugate pairs and edge-balance with the eigenvalues of graphs
provide the motivation for the new concepts of eigen-sum and eigen-product balanced
properties of classes of graphs and designs. We combine these ideas by considering eigen bibalanced
classes of graphs, where robustness and the reciprocity of the eigen-pair a,b allowed
for the ratio of the eigen-pair sum to the eigen-pair product ab, and the asymptotic
behaviour of this ratio (in terms of large values of the size of the graph/designs). The product of
the average degree of a graph with the Riemann integral of the eigen bi-balanced ratio of the
class of graphs is introduced as the area of a class of graphs/designs associated with the eigenpair.
We observe that unique area of the class of complete graphs appears to be the largest. Also,
the interval of asymptotic convergence of the eigen bi-balanced ratio, of uniquely eigen-bibalanced
classes of graphs, appears to be [1,0].
We construct a new class of graphs, called q-cliqued graphs, involving q maximal cliques of
size q, connected, and hence edge-balanced, to a central vertex. We apply the eigenvector
method to find a general conjugate eigen-pair associated with the q-cliqued graphs and then
determine the eigen-pair characteristics above for this class of graphs. The eigen-bi-balanced
ratio associated with a conjugate pair of eigenvalues of the class of q-cliqued graphs, is the same
as the eigen-bi-balanced ratio of the class of the complements of these graphs.
The q-cliqued graphs are also designs, and we use the case q 10 as an application of a
hypothetical entomological experiment involving 10 treatments and 10 blocks. We use the
design's graphical characteristics to determine a possible scheduling situation which involves
the chromatic number of its associated graph.
PREFACE
The experimental work described in this dissertation was carried out in the School of Mathematics, University of Natal, Durban, from February 2011 to November 2013, under the supervision of Dr Paul August Winter.
These studies represent original work by the author and have not otherwise been submitted in any form for any degree or diploma to any tertiary institution. Where use has been made of the work of others it is duly acknowledged in the text
Description
M. Sc. University of KwaZulu-Natal, Durban 2014.
Keywords
Graph theory., Combinatorial designs and configurations., Eigenvalues., Matrices., Charts, digrams, etc., Graphic methods., Theses--Applied mathematics.