CARTESIAN PRODUCTS OF GRAPHS AS SUBGRAPHS OF DE-BRUIJN GRAPHS OF DIMENSION AT LEAST 3

Authors
ANDREAE T HINTZ M NOLLE M SCHREIBER G SCHUSTER GW SENG H
Citation
T. Andreae et al., CARTESIAN PRODUCTS OF GRAPHS AS SUBGRAPHS OF DE-BRUIJN GRAPHS OF DIMENSION AT LEAST 3, Discrete applied mathematics, 79(1-3), 1997, pp. 3-34
Citations number
13
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
79
Issue
1-3
Year of publication
1997
Pages
3 - 34
Database
ISI
SICI code
Abstract
Given a Cartesian product G = G(1) x ... x G(M) (m greater than or equ al to 2) of nontrivial connected graphs G(i) and the base d, dimension D de Bruijn graph B(d, D), it is investigated under which conditions G is (or is not) a subgraph of B(d,D). We present a complete solution of this problem for the case D greater than or equal to 4. For D = 3, we give partial results including a complete solution for the case tha t G is a torus, i.e., G is the Cartesian product of cycles.