Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTrees with few leaves in tournaments
75
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove that there exists $C>0$ such that any $(n+Ck)$-vertex tournament contains a copy of every $n$-vertex oriented tree with $k$ leaves, improving the previously best known bound of $n+O(k^2)$ vertices to give a result tight up to the value of $C$. Furthermore, we show that, for each $k$, there exists $n_0$, such that, whenever $ngeqslant n_0$, any $(n+k-2)$-vertex tournament contains a copy of every $n$-vertex oriented tree with at most $k$ leaves, confirming a conjecture of Dross and Havet.
rate research
Read More
The {sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two combinatorial results on the number of leaves in out-branchings. We show that - every strongly connected $n$-vertex digraph $D$ with minimum in-degree at least 3 has an out-branching with at least $(n/4)^{1/3}-1$ leaves; - if a strongly connected digraph $D$ does not contain an out-branching with $k$ leaves, then the pathwidth of its underlying graph UG($D$) is $O(klog k)$. Moreover, if the digraph is acyclic, the pathwidth is at most $4k$. The last result implies that it can be decided in time $2^{O(klog^2 k)}cdot n^{O(1)}$ whether a strongly connected digraph on $n$ vertices has an out-branching with at least $k$ leaves. On acyclic digraphs the running time of our algorithm is $2^{O(klog k)}cdot n^{O(1)}$.
The Rooted Maximum Leaf Outbranching problem consists in finding a spanning directed tree rooted at some prescribed vertex of a digraph with the maximum number of leaves. Its parameterized version asks if there exists such a tree with at least $k$ leaves. We use the notion of $s-t$ numbering to exhibit combinatorial bounds on the existence of spanning directed trees with many leaves. These combinatorial bounds allow us to produce a constant factor approximation algorithm for finding directed trees with many leaves, whereas the best known approximation algorithm has a $sqrt{OPT}$-factor. We also show that Rooted Maximum Leaf Outbranching admits a quadratic kernel, improving over the cubic kernel given by Fernau et al.
Kuhn, Osthus, and Townsend asked whether there exists a constant $C$ such that every strongly $Ct$-connected tournament contains all possible $1$-factors with at most $t$ components. We answer this question in the affirmative. This is best possible up to constant. In addition, we can ensure that each cycle in the $1$-factor contains a prescribed vertex. Indeed, we derive this result from a more general result on partitioning digraphs which are close to semicomplete. More precisely, we prove that there exists a constant $C$ such that for any $kgeq 1$, if a strongly $Ck^4t$-connected digraph $D$ is close to semicomplete, then we can partition $D$ into $t$ strongly $k$-connected subgraphs with prescribed sizes, provided that the prescribed sizes are $Omega(n)$. This result improves the earlier result of Kuhn, Osthus, and Townsend. Here, the condition of connectivity being linear in $t$ is best possible, and the condition of prescribed size being $Omega(n)$ is also best possible.
In this short note we prove that every tournament contains the $k$-th power of a directed path of linear length. This improves upon recent results of Yuster and of Gir~ao. We also give a complete solution for this problem when $k=2$, showing that there is always a square of a directed path of length $lceil 2n/3 rceil-1$, which is best possible.
We consider a generalisation of Kellys conjecture which is due to Alspach, Mason, and Pullman from 1976. Kellys conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by Kuhn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number of paths needed in a path decomposition of a general tournament $T$. There is a natural lower bound for this number in terms of the degree sequence of $T$ and it is conjectured that this bound is correct for tournaments of even order. Almost all cases of the conjecture are open and we prove many of them.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
