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

DOI10.1016/S0166-218X(97)00029-2MaRDI QIDQ1372727zbMATH OpenFDO

Authors Thomas Andreae, Martin Hintz, Michael Nölle, Gerald Schreiber, Gerald W. Schuster, Hajo Seng

Publication date 4 May 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

Cartesian productde Bruijn graphsubgraph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10)

Review text

Given a Cartesian product of nontrivial connected graphs and a de Bruijn graph \(B(d,D)\) of base \(d\) and dimension \(D\), the paper studies the conditions under which the Cartesian product is a subgraph of \(B(d,D)\). It gives a complete solution to this problem for the case \(D\geq 4\). For \(D=3\) it gives partial results including a complete solution for the case that the Cartesian product is the product of cycles.

Recommendations

• Embedding Cartesian products of graphs into de Bruijn graphs
• scientific article; zbMATH DE number 1154409
• Existence of 3-regular subgraphs in Cartesian product of cycles

Cites work

• Embeddings of hypercubes and grids into de Bruijn graphs
• Graph theory
• scientific article; zbMATH DE number 4147467 (Why is no real title available?)
• scientific article; zbMATH DE number 54299 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 922847 (Why is no real title available?)
• Parallel Processing with the Perfect Shuffle
• The de Bruijn multiprocessor network: a versatile parallel processing and sorting network for VLSI

Cited in

(5)

• Embedding Cartesian products of graphs into de Bruijn graphs
• Characterizing flag graphs and incuced subgraphs of Cartesian product graphs
• scientific article; zbMATH DE number 1154409 (Why is no real title available?)
• Cartesian products of graphs as spanning subgraphs of de Bruijn graphs
• Containment properties of product and power graphs

This page was built for publication: Cartesian products of graphs as subgraphs of de Bruijn graphs of dimension at least three

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1372727)