Path: utzoo!attcan!uunet!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!B.GP.CS.CMU.EDU!Marko.Petkovsek
From: Marko.Petkovsek@B.GP.CS.CMU.EDU
Newsgroups: comp.theory
Subject: Hamiltonian circuits in complements of line graphs
Message-ID: <2495.635275203@B.GP.CS.CMU.EDU>
Date: 5 Mar 90 14:40:40 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: Marko.Petkovsek%B.GP.CS.CMU.EDU@VM1.NoDak.EDU
Lines: 14

I know that the Hamiltonian circuit problem is NP-complete for line
graphs. How about COMPLEMENTS of line graphs? A nice equivalent formulation
of this problem is the following:

   INSTANCE: Undirected graph G = (V,E).
   QUESTION: Is there a cyclic ordering of E in which any two consecutive
             edges have no vertex in common?

I would appreciate any information (or pointers to information) about the
complexity of this problem. I couldn't find it in either Garey, Johnson's
"Computers and Intractability" or in D.S. Johnson's NP-completeness columns
in Journal of Algorithms.

Marko.Petkovsek@cs.cmu.edu