A1 Refereed original research article in a scientific journal
A characterization of acyclic switching classes of graphs using forbidden subgraphs
Authors: Hage J, Harju T
Publisher: SIAM PUBLICATIONS
Publication year: 2004
Journal:: Siam Journal on Discrete Mathematics
Journal name in source: SIAM JOURNAL ON DISCRETE MATHEMATICS
Journal acronym: SIAM J DISCRETE MATH
Volume: 18
Issue: 1
First page : 159
Last page: 176
Number of pages: 18
ISSN: 0895-4801
DOI: https://doi.org/10.1137/S0895480100381890
Abstract
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.
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.
UTU Research Portal