Generalized Hadamard Matrices and 2-Factorization of Complete Graphs

Abstract

Graph factorization plays a major role in graph theory and it shares common ideas in important problems such as edge coloring and Hamiltonian cycles. A factor  of a graph  is a spanning subgraph of  which is not totally disconnected. An - factor is an - regular spanning subgraph of  and  is -factorable if there are edge-disjoint -factors  such that . We shall refer as an -factorization of a graph . In this research we consider -factorization of complete graph. A graph with  vertices is called a complete graph if every pair of distinct vertices is joined by an edge and it is denoted by . We look into the possibility of factorizing  with added limitations coming in relation to the rows of generalized Hadamard matrix over a cyclic group. Over a cyclic group  of prime order , a square matrix  of order  all of whose elements are the  root of unity is called a generalized Hadamard matrix if , where  is the conjugate transpose of matrix  and  is the identity matrix of order . In the present work, generalized Hadamard matrices over a cyclic group  have been considered. We prove that the factorization is possible for  in the case of the limitation 1, namely, If an edge  belongs to the factor , then the and  entries of the corresponding generalized Hadamard matrix should be different in the   row. In Particular,  number of rows in the generalized Hadamard matrices is used to form -factorization of complete graphs. We discuss some illustrative examples that might be used for studying the factorization of complete graphs.