Contents Online
Journal of Combinatorics
Volume 4 (2013)
Number 4
Decomposition of cartesian products of regular graphs into isomorphic trees
Pages: 469 – 490
DOI: https://dx.doi.org/10.4310/JOC.2013.v4.n4.a6
Authors
Abstract
We 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, \dots , r_k$ with ${\Sigma}^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, \dots , G_k$ such that $G_i$ is $2r_i$-regular for $1 \leq i \leq k$ decomposes into copies of $T$.
Keywords
isomorphic decomposition, cartesian product, regular graph, tree, edge-coloring
2010 Mathematics Subject Classification
05C51, 05C99
Published 27 December 2013