Graph switching, 2-ranks, and graphical Hadamard matrices

Aida Abiad, Steve Butler, Willem H. Haemers

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We study the behaviour of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil-McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order $4^m$. Starting with graphs from known Hadamard matrices of order $64$, we find (by computer) many Godsil-McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters $(63,32,16,16)$, $(64,36,20,20)$, and $(64,28,12,12)$ for almost all feasible 2-ranks. In addition we work out the behaviour of the 2-rank for a graph product related to the Kronecker product for Hadamard matrices, which enables us to find many graphical Hadamard matrices of order $4^m$ for which the related strongly regular graphs have an unbounded number of different 2-ranks. The paper extends results from the article 'Switched symplectic graphs and their 2-ranks' by the first and the last author.
Original languageEnglish
JournalDiscrete Mathematics
DOIs
Publication statusE-pub ahead of print - Dec 2018

Fingerprint

Hadamard matrices
Hadamard Matrix
Graph in graph theory
Strongly Regular Graph
Graph Products
Kronecker Product
Adjacency Matrix
Graphics

Keywords

  • strongly regular graph
  • Seidel switching
  • Godsil–McKay switching
  • 2-rank
  • Hadamard matrix

Cite this

@article{32543e53614341fdae4321d9267d1b18,
title = "Graph switching, 2-ranks, and graphical Hadamard matrices",
abstract = "We study the behaviour of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil-McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order $4^m$. Starting with graphs from known Hadamard matrices of order $64$, we find (by computer) many Godsil-McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters $(63,32,16,16)$, $(64,36,20,20)$, and $(64,28,12,12)$ for almost all feasible 2-ranks. In addition we work out the behaviour of the 2-rank for a graph product related to the Kronecker product for Hadamard matrices, which enables us to find many graphical Hadamard matrices of order $4^m$ for which the related strongly regular graphs have an unbounded number of different 2-ranks. The paper extends results from the article 'Switched symplectic graphs and their 2-ranks' by the first and the last author.",
keywords = "strongly regular graph, Seidel switching, Godsil–McKay switching, 2-rank, Hadamard matrix",
author = "Aida Abiad and Steve Butler and Haemers, {Willem H.}",
year = "2018",
month = "12",
doi = "10.1016/j.disc.2018.11.022",
language = "English",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",

}

Graph switching, 2-ranks, and graphical Hadamard matrices. / Abiad, Aida; Butler, Steve; Haemers, Willem H.

In: Discrete Mathematics, 12.2018.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Graph switching, 2-ranks, and graphical Hadamard matrices

AU - Abiad, Aida

AU - Butler, Steve

AU - Haemers, Willem H.

PY - 2018/12

Y1 - 2018/12

N2 - We study the behaviour of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil-McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order $4^m$. Starting with graphs from known Hadamard matrices of order $64$, we find (by computer) many Godsil-McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters $(63,32,16,16)$, $(64,36,20,20)$, and $(64,28,12,12)$ for almost all feasible 2-ranks. In addition we work out the behaviour of the 2-rank for a graph product related to the Kronecker product for Hadamard matrices, which enables us to find many graphical Hadamard matrices of order $4^m$ for which the related strongly regular graphs have an unbounded number of different 2-ranks. The paper extends results from the article 'Switched symplectic graphs and their 2-ranks' by the first and the last author.

AB - We study the behaviour of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil-McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order $4^m$. Starting with graphs from known Hadamard matrices of order $64$, we find (by computer) many Godsil-McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters $(63,32,16,16)$, $(64,36,20,20)$, and $(64,28,12,12)$ for almost all feasible 2-ranks. In addition we work out the behaviour of the 2-rank for a graph product related to the Kronecker product for Hadamard matrices, which enables us to find many graphical Hadamard matrices of order $4^m$ for which the related strongly regular graphs have an unbounded number of different 2-ranks. The paper extends results from the article 'Switched symplectic graphs and their 2-ranks' by the first and the last author.

KW - strongly regular graph

KW - Seidel switching

KW - Godsil–McKay switching

KW - 2-rank

KW - Hadamard matrix

U2 - 10.1016/j.disc.2018.11.022

DO - 10.1016/j.disc.2018.11.022

M3 - Article

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

ER -