Hadamard graphs from generalized hadamard matrices of order pn ; p ≥ 3 over a cyclic group ∁p

Loading...
Thumbnail Image
Date
2019-09-12
Authors
Nishadi, W. V.
Perera, A. A. I.
Journal Title
Journal ISSN
Volume Title
Publisher
University of Peradeniya
Abstract
Hadamard matrices and their applications have steadily and rapidly grown during the last two decades. This research is focused on generalized Hadamard matrices which have applications in combinatorics such as graph theory and transversal design. In our work, a mathematical method for constructing generalized Hadamard graphs corresponding to the generalized Hadamard matrix GH(p ⁿ , Cₚ), n ∈ N is introduced using the properties of Latin squares. Let C be a finite abelian group of order w. A v × v matrix M = [mᵢⱼ] with entries from C where w divides v is a generalized Hadamard matrix denoted by GH(w, v⁄w) over C if, for all i ≠ j, the sequence of quotients mᵢⱼmⱼₖ ⁻¹ , 1 ≤ k ≤ v, contains each element of C exactly v⁄w times. To construct the corresponding Latin square, cyclic shifting method is used, and the elements of the Latin square are the elements of the generalized Hadamard matrices of order pⁿ over a cyclic group Cₚ. Those Latin squares are then used to find the edges in the resulting graphs. The graph obtained in this way has 2pⁿ⁺¹ vertices labelled rᵢ ¹ , rᵢʷ, rᵢʷ² , rᵢ ʷ³ , ... , rᵢ ʷᵖ , cⱼ ¹ , cⱼ ʷ, cⱼ ʷ² , cⱼ ʷ³ , ... ,cⱼ ʷᵖ where i,j = 1, 2, ... , pⁿ . p = 3 case exists in the literature. The method was tested for p = 5, n = 1 and n = 2, and p = 7, n = 1 cases manually and the algorithm was automated. The resultant graphs for the examples are 5 −regular, 25 − regular and 7 −regular respectively. The automated algorithm can be used to construct pⁿ −regular graphs.
Description
Keywords
Generalized hadamard graphs , Latin squares , Cyclic shifting
Citation
Collections