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

Kyle F. Jao (University of Illinois, Urbana, Il., U.S.A.)

Alexandr V. Kostochka (University of Illinois, Urbana, Il., U.S.A.; Zhejiang Normal University, Jinhua, China)

Douglas B. West (University of Illinois, Urbana, Il., U.S.A.; Zhejiang Normal University, Jinhua, China)

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