Isomorphisms and traversability of directed path graphs (Q4435558)

Let \(k\) be a positive integer, and let \(D\) be a digraph containing at least one \(\vec{P}_k\). Denote by \(\vec{\Pi}_k(D)\) the set of all \(\vec{P}_k\)'s of \(D\). Then the \(\vec{P}_k\)-graph of \(D\), denoted by \(\vec{P}_k(D)\), is the digraph with vertex set \(\vec{\Pi}_k(D)\), \(pq\) is an arc of \(\vec{P}_k(D)\) if and only if there is a \(\vec{P}_{k+1}\) or \(\vec{C}_k v_1v_2 \ldots v_{k+1}\) in \(D\) (with \(v_1 = v_{k+1}\) in the case of a \(\vec{C}_k\)) such that \(p = v_1v_2\ldots v_k\) and \(q = v_2 \ldots v_kv_{k+1}\). Then \(\vec{P}_1(D) = D\) and \(\vec{P}_2(D) = \vec{L}(D)\), the line digraph of \(D\). The authors prove results of the following type: Let \(D\) be a connected digraph without sources or sinks. If \(D\) has an in-tree or an out-tree, then \(\vec{P}_3(D) \cong D\) if and only if \(D\cong \vec{C}_n\) for some \(n\geq 3\). Let \(D\) and \(D'\) be two digraphs without sources or sinks. Then every arc-isomorphism of \(D\) onto \(D'\) is induced by an isomorphism of \(D\) onto \(D'\), hence \(\vec{L}(D) \cong \vec{L}(D')\) if and only if \(D\cong D'\). Let \(D\) be a digraph such that \(\text{Asym}(\vec{L}(D))\) is strongly connected. Then (i) \(\vec{P}_3(D)\) is Eulerian if and only if \(d^-(ab) = d^+(bc)\) for each \(\vec{P}_3 abc\) in \(D\); (ii) \(\vec{P}_3(D)\) is Hamiltonian if and only if \(\vec{L}(D)\) has a \(\vec{C}_2\)-tour; (iii) \(\vec{P}_3(D)\) contains a 2-factor if and only if \(\vec{L}(D)\) is Eulerian, or, equivalently if \(d^-(v) = d^+(w)\) for each arc \(vw\) in \(D\); and (iv) \(\vec{P}_3(D)\) is Hamiltonian if \(d^-(v) = d^+(w)\) for each arc \(vw\) in \(D\), and \(D\) contains no \(\vec{C}_2\). Here \(\text{Asym}(D)\) is the graph obtained from \(D\) by deleting all \(\vec{C}_2\)'s and a Euler tour \(T\) of \(D\) is a \(\vec{C}_2\)-tour if the arcs of each \(\vec{C}_2\) of \(D\) are successive arcs in \(T\).