Combinatorics, Probability and Computing

Table of Contents - 2000 - Volume 9, Issue 03  


On Twisted Odd Graphs

M. A. FIOL a1 1 , E. GARRIGA a1 1 and J. L. A. YEBRA a1 1
a1 Departament de Matemàtica Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Jordi Girona 1-3, Mòdul C3, Campus Nord, 08034 Barcelona, Spain (e-mails: fiol@mat.upc.es, egarriga@mat.upc.es, yebra@mat.upc.es)

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.

(Received September 19 1998)
(Revised November 12 1998)


Footnotes

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.