2
$\begingroup$

Given an undirected tree and a set of directed paths in this tree (or equivalently, ordered $s$–$t$ pairs), we construct a graph with the paths as vertices and an edge between two paths if they traverse an edge of the tree in opposite directions. Is anything known about the resulting graphs? I found some similar settings, but none that exactly matches. Is this class equivalent to a known one, or does it have interesting characterizations or properties? The only thing I could find is that these graphs cannot have a $K_4$ as subgraph.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This may count only as a "similar setting," but Martin Golumbic has studied what he calls the edge intersection graph of a tree $T$, which has a node for each path in $T$, and an arc between two nodes if their paths share at least one edge. So his paths are not directed. He and coauthors have established a number of structural, coloring, and complexity properties of these "EPT" graphs, under various assumptions (e.g., on vertex degrees). Here are three references:

  • M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Mathematics 55 (1985), 151-159. (Elsevier link)

  • Golumbic, Lipshteyn, and Stern, "Representing Edge Intersection Graphs of Paths on Degree 4 Trees," Discrete Mathematics, 2008. (DeepDyve link).

  • Golumbic, Lipshteyn, and Stern, "The k-edge intersection graphs of paths in a tree," Discrete Applied Mathematics, Volume 156, Issue 4, 2008. (Elsevier link)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .