pipette
ENEnglish

The exact digirth and out-degree bounds for -subdivision and out-forest in digraphs

Bin Chen, Jianfeng Hou, Xinmin Hou, Siyue Liu, Xinjie Wang, Xinyu Zhou

Preprint

En palabras de los autores

For each integer , let denote the oriented cycle formed by two internally vertex-disjoint directed paths of length with the same initial and terminal vertices. Picasarri-Arrieta and Rambaud ({\small European J. Combin., 2024}) asked for the smallest integer such that every digraph with minimum out-degree at least two and digirth at least contains a subdivision of . We completely resolve this problem by proving that . Our proof relies on a refinement of Thomassen's theorem ({\small Discrete Math., 1985}) on two directed cycles intersecting in exactly one vertex: we prove that every digraph with minimum out-degree at least two contains two directed cycles intersecting in exactly one arc. We also establish an embedding theorem for out-forests with prescribed images of their roots, under minimum out-degree and digirth conditions determined by the number of leaves and the heights of vertices in antichains. As an application, for integers , we show that every digraph with minimum out-degree at least \(k\) and digirth at least \(k(\ell-1)+1\) contains \(k\) directed paths of length \(\ell\) sharing only their initial vertex, which can be prescribed arbitrarily. This improves the previous digirth bound \((k^\ell-1)/(k-1)+1\) of Picasarri-Arrieta and Rambaud to a sharp bound.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 15 pages,2 figures