Article
Kyungpook Mathematical Journal 2024; 64(1): 171-184
Published online March 31, 2024
Copyright © Kyungpook Mathematical Journal.
The Gallai and Anti-Gallai Graphs of Strongly Regular Graphs
Jeepamol J. Palathingal∗, Aparna Lakshmanan S., Greg Markowsky
Department of Mathematics, PM Government College, Chalakudy 680722, Kerala, India
e-mail : jeepamoljp@gmail.com
Department of Mathematics, Cochin University of Science and Technology, Cochin 682022, Kerala, India
e-mail : aparnaren@gmail.com; aparnals@cusat.ac.in
School of Mathematics, Monash University, Clayton, VIC Australia
e-mail : greg.markowsky@monash.edu
Received: January 8, 2023; Revised: November 1, 2023; Accepted: November 3, 2023
In this paper, we show that if G is strongly regular then the Gallai graph Γ(G) and the anti-Gallai graph Δ(G) of G are edge-regular. We also identify conditions under which the Gallai and anti-Gallai graphs are themselves strongly regular, as well as conditions under which they are 2-connected. We include also a number of concrete examples and a discussion of spectral properties of the Gallai and anti-Gallai graphs.
Keywords: Gallai graph, Anti-Gallai graph, Strongly regular graph, Edge-regular graph, Adjacency spectrum