ﻻ يوجد ملخص باللغة العربية
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.
We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on $n$ vertices can be decomposed into at most $leftlceil frac{n}{2}rightrceil$ paths, while
We determine the inducibility of all tournaments with at most $4$ vertices together with the extremal constructions. The $4$-vertex tournament containing an oriented $C_3$ and one source vertex has a particularly interesting extremal construction. It
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
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
We describe computer searches that prove the graph reconstruction conjecture for graphs with up to 13 vertices and some limited classes on larger sizes. We also investigate the reconstructability of tournaments up to 13 vertices and posets up to 13 p