Cartesian products of graphs as subgraphs of de Bruijn graphs of dimension at least three

被引：4

作者：

Andreae, T ^{[1
]}

Hintz, M ^{[1
]}

Nolle, M ^{[1
]}

Schreiber, G ^{[1
]}

Schuster, GW ^{[1
]}

Seng, H ^{[1
]}

机构：

[1] TECH UNIV HAMBURG,D-21071 HAMBURG,GERMANY

来源：

DISCRETE APPLIED MATHEMATICS | 1997年 / 79卷 / 1-3期

关键词：

de Bruijn graphs; Cartesian products of graphs; interconnection networks; subgraph embeddings; hypercubes; tori; parallel and distributed computing;

D O I：

10.1016/S0166-218X(97)00029-2

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Given a Cartesian product G = G(1) x ... x G(M) (m greater than or equal 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 that G is a torus, i.e., G is the Cartesian product of cycles.

引用

页码：3 / 34

页数：32