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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Casteels Sep 2 '13 at 6:35
  • $\begingroup$ 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. $\endgroup$ – Ben Sep 3 '13 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.