A characterization problem on underlying graphs of line digraphs
The underlying graph G(D) G ( D ) of a digraph D is arising when directions of edges are ignored. Chvtal and Ebenegger prove that recognising underlying graphs of line digraphs is an NP-complete problem. We note first that Chvtal and Ebengger's proof implies even more, namely that recognising underlying graphs of line digraphs of digraph in which each vertex has in-degree or out-degree at most one is an NP-complete problem. We then give a description of those underlying graphs which satisfy a supplementary condition on vertices of degree greater than two.
underlying graph line digraph