IJSTR

International Journal of Scientific & Technology Research

IJSTR@Facebook IJSTR@Twitter IJSTR@Linkedin
Home About Us Scope Editorial Board Blog/Latest News Contact Us
CALL FOR PAPERS
AUTHORS
DOWNLOADS
CONTACT
QR CODE
IJSTR-QR Code

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]

 

AUTHOR(S)

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

 

KEYWORDS

Index Terms: - Adjacency matrix , Hadamard Matrices ,k-regular 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 , 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.