Generation of Strongly Regular Graphs from Normalized Hadamard Matrices
[Full Text]
AUTHOR(S)
A. A. C. A. Jayathilake, A. A. I. Perera, M. A. P. Chamikara
KEYWORDS
Index Terms:  Adjacency matrix , Hadamard Matrices ,kregular graphs , Latin Square , Simple Graphs ,Strongly Regular Graphs, Tensor Product.
ABSTRACT
Abstract:  This paper proposes an algorithm which can be used to construct strongly regular graphs from Hadamard matrices.A graph G is strongly regular if there are integers λ and μ such that every two adjacent vertices have λ common neighbours and every two non adjacent vertices have μ common neighbors. Proposed method is mainly based on basic matrix manipulations. If the order of the normalized Hadamard matrix is n the resulting strongly regular graph will have n x n number of vertices. Therefore the simplest strongly regular graph generated from this method has 16 vertices since its predecessor normalized Hadamard matrix has the order of 4. This algorithm was implemented using C++ programming language. Then the algorithm was tested for large Hadamard matrices and the results proved that this method is correct and works for any normalized Hadamard matrix of order greater than or equal to 4.
REFERENCES
Wallis, J. S. (1975). On Hadamard matrices. Journal of Combinatorial Theory , 149164.
[2]Craigen, R. (1996). Hadamard matrices and designs. In J. H. C. J. Colbourn, CRC Handbook of Combinatorial Designs (pp. 370377). CRC Press.
[3]Graybill, F. A. (1983). Matrices, with Applications in Statistics. Belmont: Wadsworth International Group.
[4]J.J.Sylvester. (1867). Thoughts on orthogonal matrices,simultaneous sign successions and tessellated pavements in two or more colours with applications to Newton’s rule,ornamental tile work and the theory of numbers. 461475: Phil.Mag .
[5]K.J.Horadam. (2007). Hadamard matrices and generalizations . In Hadamard matrices and their applications (pp. 1012). New Jersy: Princeton University Press.
[6]Jennifer Seberry, M. Y. (1992). Hadamard matrices, sequences, and block designs. In D. J.H.Dinitz, Contemporary design theoryA collection of surveys (pp. 431560). John Wiley and sons.
[7]Harju, T. (2011). Lecture notes on graph theory.
[8]David Joyner, M. V. Algorithmic graph theory.
[9]Diestel, R. (1991). Graph Theory, Graduate Texts in Mathematics. Berlin: Springer Verlag.
[10]Prajapati, M. C. (n.d.). Distance In Graph Theory And Its Application. International Journal of Advanced Engineering Technology .
[11]West, D. (2000). Introduction to Graph Theory. Prentice Hall.
[12]Cameron, P. .. (2001). Strongly Regular Graphs. London: University of London.
[13]Brouwer, A. E. (1984). Strongly Regular Graphs and Partial Geometries. Enumeration and design:Conference on Combinatorics (pp. 85122). Waterloo: Academic press.
[14]Cormen, T. H. (2001). Representations of graphs. In Introduction to Algorithms (pp. 527531). MIT Press and McGrawHill.
[15]R.C.Bose. (1963). Strongly Regular graphs,partial geometries and partially balanced designs. Pacific Journal of Mathematics.
[16]G.H. J. van Rees. (2009). More greedy defining sets in Latin squares. Australasian Journal Of Combinatorics , 183198.
[17]Charles .J. Colbourn, (2007). The Latin square . In Handook of Combinatorial designs (pp. 135137). CRC Press.
