Path Decompositions of Tournaments

التفاصيل البيبلوغرافية
العنوان: Path Decompositions of Tournaments
المؤلفون: Daniela Kühn, Allan Lo, Deryk Osthus, Bertille Granet, António Girão
المصدر: Trends in Mathematics ISBN: 9783030838225
بيانات النشر: Springer International Publishing, 2021.
سنة النشر: 2021
مصطلحات موضوعية: Combinatorics, Path (topology), Mathematics::Combinatorics, Asymptotically optimal algorithm, Conjecture, 010201 computation theory & mathematics, 010102 general mathematics, Order (ring theory), Tournament, 0102 computer and information sciences, 0101 mathematics, 01 natural sciences, Mathematics
الوصف: In 1976, Alspach, Mason, and Pullman conjectured that any tournament T of even order can be decomposed into exactly \(\mathrm{ex}(T)\) paths, where \(\mathrm{ex}(T) = \frac{1}{2}\sum _{v\in 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.
ردمك: 978-3-030-83822-5
URL الوصول: https://explore.openaire.eu/search/publication?articleId=doi_________::ec989160a96728bb56dd0148cbcf8119
https://doi.org/10.1007/978-3-030-83823-2_31
حقوق: OPEN
رقم الأكسشن: edsair.doi...........ec989160a96728bb56dd0148cbcf8119
قاعدة البيانات: OpenAIRE