A characterization of acyclic switching classes of graphs using forbidden subgraphs

: Hage J, Harju T

Publisher: SIAM PUBLICATIONS

: 2004

Siam Journal on Discrete Mathematics

SIAM JOURNAL ON DISCRETE MATHEMATICS

: SIAM J DISCRETE MATH

: 18

: 1

: 159

: 176

: 18

: 0895-4801

DOI: https://doi.org/10.1137/S0895480100381890

We characterize the switching classes that do not contain an acyclic graph. The characterization is by means of a set of forbidden induced subgraphs. We prove that in addition to switches of the cycles C-n for n greater than or equal to 7, there are only finitely many such graphs in 24 switching classes, all having at most 9 vertices. We give a representative of each of the 24 switching classes.

Mathematics