On Twisted Odd Graphs

Abstract

The twisted odd graphs are obtained from the well-known odd graphs through an involutive automorphism. As expected, the twisted odd graphs share some of the interesting properties of the odd graphs but, in general, they seem to have a more involved structure. Here we study some of their basic properties, such as their automorphism group, diameter, and spectrum. They turn out to be examples of the so-called boundary graphs, which are graphs satisfying an extremal property that arises from a bound for the diameter of a graph in terms of its distinct eigenvalues.