Pancyclicity in Switching Classes

Andrzej Ehrenfeucht; Jurriaan Hage; Tero Harju; Grzegorz Rozenberg

doi:10.1016/S0020-0190(00)00020-X

Pancyclicity in Switching Classes

Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, Grzegorz Rozenberg

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

9 Citations (Scopus)

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 Kratochvı́l et al. (1992)) although this problem is NP-complete for graphs.

Original language	English
Pages (from-to)	153-156
Number of pages	4
Journal	Information Processing Letters
Volume	73
Issue number	5-6
DOIs	https://doi.org/10.1016/S0020-0190(00)00020-X
Publication status	Published - 31 Mar 2000

Keywords

Mathematics
Informatica
Landbouwwetenschappen
Natuurwetenschappen

Access to Document

10.1016/S0020-0190(00)00020-X

Cite this

@article{13190c6cd96e48fca068798af20cdf7b,

title = "Pancyclicity in Switching Classes",

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 Kratochv{\'ı}l et al. (1992)) although this problem is NP-complete for graphs.",

keywords = "Mathematics, Informatica, Landbouwwetenschappen, Natuurwetenschappen",

author = "Andrzej Ehrenfeucht and Jurriaan Hage and Tero Harju and Grzegorz Rozenberg",

year = "2000",

month = mar,

day = "31",

doi = "10.1016/S0020-0190(00)00020-X",

language = "English",

volume = "73",

pages = "153--156",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5-6",

}

TY - JOUR

T1 - Pancyclicity in Switching Classes

AU - Ehrenfeucht, Andrzej

AU - Hage, Jurriaan

AU - Harju, Tero

AU - Rozenberg, Grzegorz

PY - 2000/3/31

Y1 - 2000/3/31

N2 - 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.

AB - 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.

KW - Mathematics

KW - Informatica

KW - Landbouwwetenschappen

KW - Natuurwetenschappen

U2 - 10.1016/S0020-0190(00)00020-X

DO - 10.1016/S0020-0190(00)00020-X

M3 - Article

SN - 0020-0190

VL - 73

SP - 153

EP - 156

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5-6

ER -

Pancyclicity in Switching Classes

Abstract

Keywords

Access to Document

Fingerprint

Cite this