International Journal of Scientific & Technology Research

Home About Us Scope Editorial Board Blog/Latest News Contact Us
10th percentile
Powered by  Scopus
Scopus coverage:
Nov 2018 to May 2020


IJSTR >> Volume 2- Issue 2, February 2013 Edition

International Journal of Scientific & Technology Research  
International Journal of Scientific & Technology Research

Website: http://www.ijstr.org

ISSN 2277-8616

Generation of Strongly Regular Graphs from Normalized Hadamard Matrices

[Full Text]



A. A. C. A. Jayathilake, A. A. I. Perera, M. A. P. Chamikara



Index Terms: - Adjacency matrix , Hadamard Matrices ,k-regular graphs , Latin Square , Simple Graphs ,Strongly Regular Graphs, Tensor Product.



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.



Wallis, J. S. (1975). On Hadamard matrices. Journal of Combinatorial Theory , 149-164.

[2]Craigen, R. (1996). Hadamard matrices and designs. In J. H. C. J. Colbourn, CRC Handbook of Combinatorial Designs (pp. 370-377). 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. 461-475: Phil.Mag .

[5]K.J.Horadam. (2007). Hadamard matrices and generalizations . In Hadamard matrices and their applications (pp. 10-12). New Jersy: Princeton University Press.

[6]Jennifer Seberry, M. Y. (1992). Hadamard matrices, sequences, and block designs. In D. J.H.Dinitz, Contemporary design theory-A collection of surveys (pp. 431-560). 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. 85-122). Waterloo: Academic press.

[14]Cormen, T. H. (2001). Representations of graphs. In Introduction to Algorithms (pp. 527-531). MIT Press and McGraw-Hill.

[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 , 183-198.

[17]Charles .J. Colbourn, (2007). The Latin square . In Handook of Combinatorial designs (pp. 135-137). CRC Press.