A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
A characterization of acyclic switching classes of graphs using forbidden subgraphs
Tekijät: Hage J, Harju T
Kustantaja: SIAM PUBLICATIONS
Julkaisuvuosi: 2004
Lehti:: Siam Journal on Discrete Mathematics
Tietokannassa oleva lehden nimi: SIAM JOURNAL ON DISCRETE MATHEMATICS
Lehden akronyymi: SIAM J DISCRETE MATH
Vuosikerta: 18
Numero: 1
Aloitussivu: 159
Lopetussivu: 176
Sivujen määrä: 18
ISSN: 0895-4801
DOI: https://doi.org/10.1137/S0895480100381890
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali