Matrices of graphs and designs with emphasis on their integral eigen-pair balance characteristic.

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