| Authors: | J. Hage, T. Harju |
| Contact: | WWW: Theoretical Computer Science |
| Date: | March 2000 |
| Download: | http://www.liacs.nl/TechRep/2000/tr00-05.ps.gz |
Abstract:
We characterize the switching classes that do not contain an
acyclic graph. The characterization is by means of a set of
forbidden graphs. We prove that in addition to switches of the cycles
Cn for n >= 7 there are only finitely many such graphs. In fact,
there are no such graphs with more than 9 vertices. We give a
representative of each of the 24 classes.
Submitted to Eur. Jnl. Comb.