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

共 13 条

[1]

ANDREAE T, 1994, LECT NOTES COMPUTER, V903, P140

[2]

[Anonymous], COMP SUPPL

[3]

BERMOND JC, 1989, HYPERCUBE AND DISTRIBUTED COMPUTERS, P279

[4]

BERMOND JC, 1992, INTERCONNECTION NETW

[5]

BONDY JA, 1976, GRAPH THEORY APPLICA

[6]

BURKHARDT H, 1991, ESPRIT BRA 3035 WORK, P65

[7] EMBEDDINGS OF HYPERCUBES AND GRIDS INTO DE BRUIJN GRAPHS [J].

HEYDEMANN, MC ;

OPATRNY, J ;

SOTTEAU, D .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1994, 23 (01) :104-111

[8]

HEYDEMANN MC, 1991, 723 LRI U PAR SUD

[9]

HINTZ M, 1995, LADDERS DEBRUIJN GRA

[10]

Leighton F.T., 1992, Introduction to Parallel Algorithms and Architecture: Arrays. Trees. Hypercubes

← 1 2 →