Decomposition of cartesian products of regular graphs into isomorphic trees
Kyle F. Jao, Alexandr V. Kostochka, Douglas B. West · Journal of Combinatorics · 2013
Dedicated to the memory of Hunter SnevilyWe extend the ideas of Snevily and Avgustinovitch to enlarge the families of 2m-regular graphs and m-regular bipartite graphs that are known to decompose into isomorphic copies of a tree T with m edges.For example, consider r 1 , . . ., r k with k i=1 r i = m.If T has a k-edge-coloring with r i edges of color i such that every path in T uses some color once or twice, then every cartesian product of graphs G 1 , . . ., G k such that G i is 2r i -regular for 1 ≤ i ≤ k decomposes into copies of T .