𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Embedding Cartesian Products of Graphs into de Bruijn Graphs

✍ Scribed by Thomas Andreae; Michael Nölle; Gerald Schreiber

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
172 KB
Volume
46
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

Given a Cartesian product G

of nontrivial connected graphs G i and the n-dimensional base B de Bruijn graph D = D B (n), it is investigated whether or not G is a spanning subgraph of D. Special attention is given to graphs G 1 × • • • × G m which are relevant for parallel computing, namely, to Cartesian products of paths ( grids) or cycles (tori). For 2-dimensional de Bruijn graphs D, we present a theorem stating that certain structural assumptions on the factors G 1 , . . . , G m ensure that G 1 × • • • × G m is a spanning subgraph of D. As corollaries, we obtain results improving previous results of Heydemann et al. (J. Parallel Distrib. Comput. 23 (1994), 104-111) on embedding grids and tori into de Bruijn graphs. Specifically, we obtain that (i) any grid G = G 1 × • • • × G m is a spanning subgraph of D = D B (2) provided that |G| = |D|, and (ii) any torus G = G 1 × • • • × G m is a spanning subgraph of D = D B (2) provided that |G| = |D| and that the G i are cycles of even length ≥4. We show that these results have consequences for the case n > 2, too: for even n, we apply our results to obtain embeddings of grids and tori G into de Bruijn graphs D B (n) with dilation n/2, where the base B is a fixed integer ≥2, and n is big enough to ensure |G| ≤ |D B (n)|. We also contrast our results for n = 2 with nonexistence results for n ≥ 3 and briefly describe experimental results in the area of parallel image processing.

📜 SIMILAR VOLUMES

Embeddings of cartesian products of near
Embeddings of cartesian products of nearly bipartite graphs
✍ Bojan Mohar; Tomaž Pisanski; Arthur T. White 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

## Abstract Surgical techniques are often effective in constructing genus embeddings of cartesian products of bipartite graphs. In this paper we present a general construction that is “close” to a genus embedding for cartesian products, where each factor is “close” to being bipartite. In specializi

2-diameter of de Bruijn graphs
2-diameter of de Bruijn graphs
✍ Li, Qiao; Sotteau, Dominique; Xu, Junming 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 589 KB

This paper shows that in the undirected binary de Bruijn graph of dimension n . UB(n), which has diameter n , there exist at least two internally vertex disjoint paths of length at most n between any two vertices. In other words, the 2-diameter of U B ( n ) is equal to its diameter n .

Cartesian Products of Graphs and Metric
Cartesian Products of Graphs and Metric Spaces
✍ S. Avgustinovich; D. Fon-Der-Flaass 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 68 KB

We prove uniqueness of decomposition of a finite metric space into a product of metric spaces for a wide class of product operations. In particular, this gives the positive answer to the long-standing question of S. Ulam: 'If U × U V × V with U , V compact metric spaces, will then U and V be isometr

On the embedding of graphs into graphs w
On the embedding of graphs into graphs with few eigenvalues
✍ Vu, Van H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 726 KB

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic

Circular chromatic index of Cartesian pr
Circular chromatic index of Cartesian products of graphs
✍ Douglas B. West; Xuding Zhu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB

## Abstract The __circular chromatic index__ of a graph __G__, written $\chi\_{c}'(G)$, is the minimum __r__ permitting a function $f : E(G)\rightarrow [0,r)$ such that $1 \le | f(e)-f(e')|\le r - 1$ whenever __e__ and $e'$ are incident. Let $G = H$ □ $C\_{2m +1}$, where □ denotes Cartesian product

Game coloring the Cartesian product of g
Game coloring the Cartesian product of graphs
✍ Xuding Zhu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB

## Abstract This article proves the following result: Let __G__ and __G__′ be graphs of orders __n__ and __n__′, respectively. Let __G__^\*^ be obtained from __G__ by adding to each vertex a set of __n__′ degree 1 neighbors. If __G__^\*^ has game coloring number __m__ and __G__′ has acyclic chromat