A characterization of acyclic switching classes using forbidden subgraphs

Jurriaan Hage; Tero Harju

doi:10.1137/S0895480100381890

A characterization of acyclic switching classes using forbidden subgraphs

Jurriaan Hage, Tero Harju

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

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 Cn for $n\geq 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.

Original language	English
Pages (from-to)	159-176
Number of pages	18
Journal	SIAM Journal on Discrete Mathematics
Volume	18
Issue number	1
DOIs	https://doi.org/10.1137/S0895480100381890
Publication status	Published - 2005

Access to Document

10.1137/S0895480100381890

Cite this

@article{88a99fabac5f4f498b4965b63c3c70bd,

title = "A characterization of acyclic switching classes using forbidden subgraphs",

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 Cn for \$n\textbackslash{}geq 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.",

author = "Jurriaan Hage and Tero Harju",

note = "HH:critical",

year = "2005",

doi = "10.1137/S0895480100381890",

language = "English",

volume = "18",

pages = "159--176",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - A characterization of acyclic switching classes using forbidden subgraphs

AU - Hage, Jurriaan

AU - Harju, Tero

N1 - HH:critical

PY - 2005

Y1 - 2005

N2 - 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 Cn for $n\geq 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.

AB - 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 Cn for $n\geq 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.

U2 - 10.1137/S0895480100381890

DO - 10.1137/S0895480100381890

M3 - Article

SN - 0895-4801

VL - 18

SP - 159

EP - 176

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -

A characterization of acyclic switching classes using forbidden subgraphs

Abstract

Access to Document

Fingerprint

Cite this