MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let G be a directed multigraph, and let H be the induced directed graph whose vertices are the edges of G, and whose edges are given by pairs of consecutive edges in G; i.e., there is an edge from v to w in H if and only if the terminal vertex of v in G is the initial vertex of w. In the case where G has no extremal vertices, is G recoverable from H? If so, is there an equivalence of categories between directed multigraphs without extremal vertices and directed graphs without extremal vertices, given by forming the induced graph?

share|cite|improve this question
The construction you describe is called forming the line digraph (also called the arc digraph.) Question: What is an extremal vertex? Do you mean a vertex of degree 0 or 1? Or do you mean a source or a sink? – Casteels Sep 2 '13 at 6:35
Casteels, thanks for the terminology... that helps me search. I mean a source or a sink. I just found the "object-level" result in a 1960 paper of Harary and Norman (theorem 3). I still don't know if the category-level equivalence has been proven. – Ben Sep 3 '13 at 8:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.