[comp.theory] Hamiltonian circuits in complements of line graphs

Marko.Petkovsek@B.GP.CS.CMU.EDU (03/05/90)

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