Pancyclicity in switching classes



: Ehrenfeucht A, Hage J, Harju T, Rozenberg G

Publisher: ELSEVIER SCIENCE BV

: 2000

Information Processing Letters

INFORMATION PROCESSING LETTERS

: INFORM PROCESS LETT

: 73

: 5-6

: 153

: 156

: 4

: 0020-0190

DOI: https://doi.org/10.1016/S0020-0190(00)00020-X


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.



Last updated on 2025-13-10 at 14:15