On Twisted Odd Graphs
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.(Received September 19 1998)
(Revised November 12 1998)
1 Work supported in part by the Spanish Research Council (Comisión Interministerial de Ciencia y Tecnología, CICYT) under projects TIC 94-0592 and TIC 97-0963.