Contents Online

# Journal of Combinatorics

## Volume 4 (2013)

### Number 4

### Decomposition of cartesian products of regular graphs into isomorphic trees

Pages: 469 – 490

DOI: http://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