On the Existence of $S$-Graphs

Abstract

We answer in the affirmative a question posed by Al-Addasi and Al-Ezeh in 2008 on the existence of symmetric diametrical bipartite graphs of diameter 4. Bipartite symmetric diametrical graphs are called $S$-graphs by some authors, and diametrical graphs have also been studied by other authors using different terminology, such as self-centered unique eccentric point graphs. We include a brief survey of some of this literature and note that the existence question was also answered by Berman and Kotzig in a 1980 paper, along with a study of different isomorphism classes of these graphs using a $(1,-1)$-matrix representation which includes the well-known Hadamard matrices. Our presentation focuses on a neighborhood characterization of $S$-graphs, and we conclude our survey with a beautiful version of this characterization known to Janakiraman.