Pancyclicity in Switching Classes

Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, Grzegorz Rozenberg

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


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 Kratochvı́l et al. (1992)) although this problem is NP-complete for graphs.
Original languageEnglish
Pages (from-to)153-156
Number of pages4
JournalInformation Processing Letters
Issue number5-6
Publication statusPublished - 31 Mar 2000


  • Mathematics
  • Informatica
  • Landbouwwetenschappen
  • Natuurwetenschappen


Dive into the research topics of 'Pancyclicity in Switching Classes'. Together they form a unique fingerprint.

Cite this