اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn 1-factors with prescribed lengths in tournaments
100
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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.
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 the
re 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.
In 1976, Alspach, Mason, and Pullman conjectured that any tournament $T$ of even order can be decomposed into exactly ${rm ex}(T)$ paths, where ${rm ex}(T):= frac{1}{2}sum_{vin V(T)}|d_T^+(v)-d_T^-(v)|$. We prove this conjecture for all sufficiently
large tournaments. We also prove an asymptotically optimal result for tournaments of odd order.
Let $S_k(n)$ be the maximum number of orientations of an $n$-vertex graph $G$ in which no copy of $K_k$ is strongly connected. For all integers $n$, $kgeq 4$ where $ngeq 5$ or $kgeq 5$, we prove that $S_k(n) = 2^{t_{k-1}(n)}$, where $t_{k-1}(n)$ is t
he number of edges of the $n$-vertex $(k-1)$-partite Turan graph $T_{k-1}(n)$, and that $T_{k-1}(n)$ is the only $n$-vertex graph with this number of orientations. Furthermore, $S_4(4) = 40$ and this maximality is achieved only by $K_4$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
