Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T04:13:27.197Z Has data issue: false hasContentIssue false

Decomposing cubes

Part of:Graph theory

Published online by Cambridge University Press:  09 April 2009

P. Horak
Affiliation:
Slovak Technical University81219 Bratislava, Slovakia
J. Širáň
Affiliation:
Comenius University84215 Bratislava, Slovakia
W. Wallis
Affiliation:
Southern Illinois UniversityCarbondale Illinois 62901
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A graph H decomposes into a graph G if one can write H as an edge-disjoint union of graphs isomorphic to G. H decomposes into D, where D is a family of graphs, when H can be written as a union of graphs each isomorphic to some member of D, and every member of D is represented at least once. In this paper it is shown that the d-dimensional cube Qd decomposes into any graph G of size d each of whose blocks is either an even cycle or an edge. Furthennore, Qd decomposes into D, where D is any set of six trees of size d.

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1996