Some digraph classes that meet the directed path partition conjecture
Let \(D\) be a digraph, and \(\lambda(D)\) be the length of a longest directed path in \(D\). The directed path partition conjecture (DPPC) says that for every \(q \in \{ 1, 2, \dotsc, \lambda(D) - 1 \}\) there is a partition \((A,B)\) of \(V(D)\) such that \(\lambda(D[A]) \leq q\) and \(\lambda[D(B)] \leq \lambda(D) - q\). This paper proves the DPPC for certain graph classes.\N\NA digraph \(D\) is said to be \(k\)-quasi-transitive if, whenever there is a directed path of length \(k\) from \(u\) to \(v\), then we have that \(u\) and \(v\) are adjacent in \(D\). Given a digraph \(H\) with vertex set \(\{u_{1},\dotsc,u_{t}\}\), and digraphs \(D_{1},\dotsc,D_{t}\), the composition over \(H\) with \(D_{1},\dotsc,D_{t}\) is the digraph \(H[D_{1},\dotsc,D_{t}]\) defined as the disjoint union of \(D_{1},\dotsc,D_{t}\) along with the arcs \((v,w)\) where \(v \in V(D_{i})\) and \(w \in V(D_{j})\) such that \((u_{i},u_{j})\) is an arc of \(H\).\N\NIn the first half of the paper, the authors show that non-strong \(3\)-quasi-transitive digraphs and strong \(4\)-transitive digraphs satisfy the DPPC. The authors use the structural characterizations of such graphs by \textit{H. Galeana-Sánchez} et al. [Discrete Math. 310, No. 19, 2495--2498 (2010; Zbl 1213.05112)], \textit{S. Wang} and \textit{R. Wang} [ibid. 311, No. 4, 282--288 (2011; Zbl 1222.05090)] and \textit{C. Hernández-Cruz} [Discuss. Math., Graph Theory 33, No. 2, 247--260 (2013; Zbl 1293.05136)] to prove their results. From the result of \textit{A. Arroyo} and \textit{H. Galeana-Sánchez} [Discrete Math. 313, No. 3, 293--300 (2013; Zbl 1256.05085)] that strong \(3\)-quasi-transitive digraphs satisfy the DPPC, the conjecture is now known to be satisfied by all \(3\)-quasi-transitive digraphs.\N\NIn the second half of the paper, the authors prove two results on compositions over unicyclic digraphs. First, let \(T\) be a unicyclic digraph on the vertex set \(\{v_{1},\dotsc,v_{n}\}\) with \(C = v_{1}v_{2}\dotsm v_{t}v_{1}\) being the unique cycle in \(T\), and let \(D_{1},\dotsc,D_{n}\) be digraphs such that \(D_{1},\dotsc,D_{t}\) have the same order, and \(D_{t+1},\dotsc,D_{n}\) each satisfy the DPPC. Then, \(T[D_{1},\dotsc,D_{n}]\) satisfies the DPPC. Second, if \(C = v_{1}v_{2} \dotsm v_{t} v_{1}\) is a cycle and \(D_{1},\dotsc,D_{t}\) are any digraphs, then \(C[D_{1},\dotsc,D_{t}]\) satisfies the DPPC. These results generalize an earlier result of Arroyo-Galeana-Sánchez [loc. cit.] on sufficient conditions for a composition to satisfy the DPPC.
- 4-transitive digraphs. I: The structure of strong 4-transitive digraphs
- A survey of the path partition conjecture
- Extended path partition conjecture for semicomplete and acyclic compositions
- scientific article; zbMATH DE number 3838057 (Why is no real title available?)
- Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs
- Longest path partitions in generalizations of tournaments
- On the structure of strong 3-quasi-transitive digraphs
- The directed path partition conjecture
- The Path Partition Conjecture is true for some generalizations of tournaments
This page was built for publication: Some digraph classes that meet the directed path partition conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6969944)
