Graph switching, 2-ranks, and graphical Hadamard matrices

Aida Abiad Monge; S. Butler; Willem Haemers

doi:10.1016/j.disc.2018.11.022

Graph switching, 2-ranks, and graphical Hadamard matrices

Aida Abiad Monge, S. Butler, Willem Haemers^*

^*Corresponding author for this work

QE Operations research

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

We study the behavior 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 behavior 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 number of related strongly regular graphs with different 2-ranks is unbounded as a function of m. The paper extends results from the article ''Switched symplectic graphs and their 2-ranks'' by the first and the last author.

Original language	English
Pages (from-to)	2850-2855
Number of pages	6
Journal	Discrete Mathematics
Volume	342
Issue number	10
DOIs	https://doi.org/10.1016/j.disc.2018.11.022
Publication status	Published - Oct 2019
Event	Algebraic and Extremal Graph Theory Conference - University of Delaware, Newark, United States Duration: 7 Aug 2017 → 10 Aug 2017

Keywords

Strongly regular graph
Seidel switching
Godsil-McKay switching
2-rank
Hadamard matrix
STRONGLY REGULAR GRAPHS

Access to Document

10.1016/j.disc.2018.11.022Licence: Free access - publisher

Cite this

@article{dea52183e3244e459c36ba491d48136e,

title = "Graph switching, 2-ranks, and graphical Hadamard matrices",

abstract = "We study the behavior 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 behavior 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 number of related strongly regular graphs with different 2-ranks is unbounded as a function of m. 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, STRONGLY REGULAR GRAPHS",

author = "{Abiad Monge}, Aida and S. Butler and Willem Haemers",

note = "data source: no data used; Algebraic and Extremal Graph Theory Conference ; Conference date: 07-08-2017 Through 10-08-2017",

year = "2019",

month = oct,

doi = "10.1016/j.disc.2018.11.022",

language = "English",

volume = "342",

pages = "2850--2855",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "10",

}

TY - JOUR

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

AU - Abiad Monge, Aida

AU - Butler, S.

AU - Haemers, Willem

N1 - data source: no data used

PY - 2019/10

Y1 - 2019/10

N2 - We study the behavior 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 behavior 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 number of related strongly regular graphs with different 2-ranks is unbounded as a function of m. 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 behavior 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 behavior 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 number of related strongly regular graphs with different 2-ranks is unbounded as a function of m. 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

KW - STRONGLY REGULAR GRAPHS

U2 - 10.1016/j.disc.2018.11.022

DO - 10.1016/j.disc.2018.11.022

M3 - Article

SN - 0012-365X

VL - 342

SP - 2850

EP - 2855

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10

T2 - Algebraic and Extremal Graph Theory Conference

Y2 - 7 August 2017 through 10 August 2017

ER -