Hadamard Graph

An -Hadamard graph is a graph on vertices defined in terms of a Hadamard matrix as follows. Define symbols , , , and , where stands for "row" and stands for "columns," and take these as the vertices of the graph. Then construct two edges for each matrix element such that and for each matrix element such that (Brouwer et al. 1989, p. 19).

An -Hadamard graph therefore exists for each value of for which a corresponding Hadamard matrix exists, which is , 2, and conjectured to be for all divisible by 4, with the smallest such value for which this remains uncertain as of Jan. 2009 is . Multiple distinct Hadamard matrices may exist of a given order, but their corresponding Hadamard graphs are not necessarily distinct. While the numbers of different Hadamard matrices of orders 4, 8, 16, ... are 1, 1, 1, 5, 3, 60, 487, ..., the corresponding numbers of nonisomorphic Hadamard graphs are 1, 1, 1, 4, 3, 36, 294, ....

Note that there appear to be two variants in the definition for Hadamard matrices. In particular, Wallis (1988, p. 165) requires that half the vertices of a Hadamard graph (those corresponding to rows) be given self-loops while the rest of the vertices (corresponding to columns) should not. In contrast, the definition of Brouwer et al. (1989, p. 19), which is the one adopted here, omits such self-loops. Note that while Hadamard graphs with self-loops can be used as a tool for determining equivalence of Hadamard matrices, those without cannot (L. Baird, pers. comm., Nov. 2008).

An -Hadamard graph is distance-regular with intersection array (Brouwer et al. 1989, p. 19). An -Hadamard graph is distance-transitive if is a power of 2 or if (Brouwer et al. 1989, pp. 227-228).

Special cases are summarized in the following table.

	-Hadamard graph
1	2-ladder rung graph
2	cycle graph
4	tesseract graph