A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Pancyclicity in switching classes
Tekijät: Ehrenfeucht A, Hage J, Harju T, Rozenberg G
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2000
Lehti:: Information Processing Letters
Tietokannassa oleva lehden nimi: INFORMATION PROCESSING LETTERS
Lehden akronyymi: INFORM PROCESS LETT
Vuosikerta: 73
Numero: 5-6
Aloitussivu: 153
Lopetussivu: 156
Sivujen määrä: 4
ISSN: 0020-0190
DOI: https://doi.org/10.1016/S0020-0190(00)00020-X
Tiivistelmä
Switching classes of graphs were introduced by van Lint and Seidel in the context of equiangular lines in elliptic geometry. We show that every switching class, except the class of all complete bipartite graphs, contains a pancyclic graph. This implies that deciding whether a switching class contains a hamiltonian graph can be done in polynomial time (as was noted by Kratochvil et al. (1992)) although this problem is NP-complete for graphs. (C) 2000 Elsevier Science B.V. All rights reserved.
Switching classes of graphs were introduced by van Lint and Seidel in the context of equiangular lines in elliptic geometry. We show that every switching class, except the class of all complete bipartite graphs, contains a pancyclic graph. This implies that deciding whether a switching class contains a hamiltonian graph can be done in polynomial time (as was noted by Kratochvil et al. (1992)) although this problem is NP-complete for graphs. (C) 2000 Elsevier Science B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali