๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Matrix Representation of Graph Embedding in a Hypercube

โœ Scribed by Y.C. Tseng; T.H. Lai; L.F. Wu

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
707 KB
Volume
23
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

The purpose of this paper is to demonstrate the use of matrices for the representation of graph embedding in a hypercube. We denote the image of an embedding (which is a subgraph of the hypercube) as a matrix. With this representation, we are able to simplify, unify, generalize, or improve existing results regarding multigraph embedding in a hypercube. A class of trees called regular binary-reflected trees is identified, which includes linear paths, binomial trees, and many others. We show that for any regular binary-reflected tree (T, n) copies of (T) can be simultaneously embedded in an (n)-cube with congestion (=2). Embeddings of binary trees and meshes are also discussed. 1994 Academic Press. Inc.

๐Ÿ“œ SIMILAR VOLUMES

Small congestion embedding of graphs int
Small congestion embedding of graphs into hypercubes
โœ Matsubayashi, Akira; Ueno, Shuichi ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 103 KB ๐Ÿ‘ 1 views

We consider the problem of embedding graphs into hypercubes with minimal congestion. Kim and Lai showed that for a given N-vertex graph G and a hypercube it is NP-complete to determine whether G is embeddable in the hypercube with unit congestion, but G can be embedded with unit congestion in a hype

Embeddings of Hypercubes and Grids into
Embeddings of Hypercubes and Grids into de Bruijn Graphs
โœ M.C. Heydemann; J. Opatrny; D. Sotteau ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 644 KB

An embedding of a graph \(G\) into a graph \(H\) is an injective mapping \(f\) from the vertices of \(G\) into the vertices of \(H\) together with a mapping \(P_{f}\) of edges of \(G\) into paths in \(H\). The dilation of the embedding is the maximum taken over all the lengths of the paths \(P_{f}(x