A1 Refereed original research article in a scientific journal
Pancyclicity in switching classes
Authors: Ehrenfeucht A, Hage J, Harju T, Rozenberg G
Publisher: ELSEVIER SCIENCE BV
Publication year: 2000
Journal:: Information Processing Letters
Journal name in source: INFORMATION PROCESSING LETTERS
Journal acronym: INFORM PROCESS LETT
Volume: 73
Issue: 5-6
First page : 153
Last page: 156
Number of pages: 4
ISSN: 0020-0190
DOI: https://doi.org/10.1016/S0020-0190(00)00020-X
Abstract
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.
UTU Research Portal