Decomposing highly edge-connected graphs into paths of any given length

详细信息    查看全文

• 作者：F. Botler ^{fbotler@ime.usp.br} ; G.O. Mota ^{mota@ime.usp.br} ; M.T.I. Oshiro ^{oshiro@ime.usp.br} ; Y. Wakabayashi ^{yw@ime.usp.br}
• 关键词：Path ; Decomposition ; Connectivity
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：508-542
• 全文大小：784 K
• 卷排序：122

文摘

In 2006, Barát and Thomassen posed the following conjecture: for each tree T  , there exists a natural number kTkT such that, if G   is a kTkT-edge-connected graph and |E(G)||E(G)| is divisible by |E(T)||E(T)|, then G admits a decomposition into copies of T  . This conjecture was verified for stars, some bistars, paths of length 3, 5, and 2r2r for every positive integer r. We prove that this conjecture holds for paths of any fixed length.