A survey of the theory of hypercube graphs (Q1102985): Difference between revisions

We present a comprehensive survey of the theory of hypercube graphs. Basic properties related to distance, coloring, domination and genus are reviewed. The properties of the n-cube defined by its subgraphs are considered next, including thickness, Hamiltonian cycles and induced paths and cycles. Finally, various embedding and packing problems are discussed, including the determination of the cubical dimension of a given cubical graph.

0 references

zbMATH Keywords

survey

0 references

hypercube graphs

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Parallel concepts in graph theory

0 references

A lower bound for crossing numbers of graphs with application to $K_n$,$K_{pq}$g, and $Q(d)$

0 references

Q3270978

0 references

Maximum versus minimum invariants for graphs

0 references

Towards a theory of domination in graphs

0 references

Q3947698

0 references

Über drei kombinatorische Probleme am $n$-dimensionalen Würfel und Würfelgitter

0 references

The Genus of the n-Cube

0 references

On the Stable Crossing Number of Cubes

0 references

Die dicke des n-dimensionalen Würfel-graphen

0 references

Bounds on the Coarseness of the n-Cube

0 references

Bounds on the number of Hamiltonian circuits in the n-cube

0 references

On the Number of Hamiltonian Circuits in the n-Cube

0 references

Cospectral Graphs and Digraphs

0 references

Q5613844

0 references

Acquaintance Graph Party Problem

0 references

A characterization of hypercubes

0 references

On cubical graphs

0 references

Another characterization of hypercubes

0 references

A characterization of the n-cube by convex subgraphs

0 references

Convexity in graphs

0 references

A Graph Model for Fault-Tolerant Computing Systems

0 references

Q5663904

0 references

On Homeomorphic Embeddings of Km,n in the Cube

0 references

Proof of the squashed cube conjecture

0 references

$B$-valuations of graphs

0 references

On Hamiltonian circuits and spanning trees of hypercubes

0 references

Q3041106

0 references

Embedding the dichotomic tree into the $n$-cube

0 references

Embedding the polytomic tree into the $n$-cube

0 references

One-legged caterpillars span hypercubes

0 references

On cubes and dichotomic trees

0 references

On quasistars in $n$-cubes

0 references

The starlike trees which span a hypercube

0 references

Smallest maximal matchings in the graph of the d-dimensional cube

0 references

Identifiers

zbMATH Open document ID

0645.05061

0 references

DOI

10.1016/0898-1221(88)90213-1

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1102985

@@ Property / cites work @@
+Parallel concepts in graph theory
@@ Property / cites work: Parallel concepts in graph theory / rank @@
+Normal rank
@@ Property / cites work @@
+A lower bound for crossing numbers of graphs with application to \(K_n\),\(K_{pq}\)g, and \(Q(d)\)
+Normal rank
@@ Property / cites work @@
+Q3270978
@@ Property / cites work: Q3270978 / rank @@
+Normal rank
@@ Property / cites work @@
+Maximum versus minimum invariants for graphs
@@ Property / cites work: Maximum versus minimum invariants for graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Towards a theory of domination in graphs
@@ Property / cites work: Towards a theory of domination in graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3947698
@@ Property / cites work: Q3947698 / rank @@
+Normal rank
@@ Property / cites work @@
+Über drei kombinatorische Probleme am \(n\)-dimensionalen Würfel und Würfelgitter
+Normal rank
@@ Property / cites work @@
+The Genus of the <i>n</i>-Cube
@@ Property / cites work: The Genus of the <i>n</i>-Cube / rank @@
+Normal rank
@@ Property / cites work @@
+On the Stable Crossing Number of Cubes
@@ Property / cites work: On the Stable Crossing Number of Cubes / rank @@
+Normal rank
@@ Property / cites work @@
+Die dicke des n-dimensionalen Würfel-graphen
@@ Property / cites work: Die dicke des n-dimensionalen Würfel-graphen / rank @@
+Normal rank
@@ Property / cites work @@
+Bounds on the Coarseness of the <i>n</i>-Cube
@@ Property / cites work: Bounds on the Coarseness of the <i>n</i>-Cube / rank @@
+Normal rank
@@ Property / cites work @@
+Bounds on the number of Hamiltonian circuits in the n-cube
+Normal rank
@@ Property / cites work @@
+On the Number of Hamiltonian Circuits in the n-Cube
+Normal rank
@@ Property / cites work @@
+Cospectral Graphs and Digraphs
@@ Property / cites work: Cospectral Graphs and Digraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q5613844
@@ Property / cites work: Q5613844 / rank @@
+Normal rank
@@ Property / cites work @@
+Acquaintance Graph Party Problem
@@ Property / cites work: Acquaintance Graph Party Problem / rank @@
+Normal rank
@@ Property / cites work @@
+A characterization of hypercubes
@@ Property / cites work: A characterization of hypercubes / rank @@
+Normal rank
@@ Property / cites work @@
+On cubical graphs
@@ Property / cites work: On cubical graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Another characterization of hypercubes
@@ Property / cites work: Another characterization of hypercubes / rank @@
+Normal rank
@@ Property / cites work @@
+A characterization of the n-cube by convex subgraphs
+Normal rank
@@ Property / cites work @@
+Convexity in graphs
@@ Property / cites work: Convexity in graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A Graph Model for Fault-Tolerant Computing Systems
+Normal rank
@@ Property / cites work @@
+Q5663904
@@ Property / cites work: Q5663904 / rank @@
+Normal rank
@@ Property / cites work @@
+On Homeomorphic Embeddings of <i>K<sub>m,n</sub></i> in the Cube
+Normal rank
@@ Property / cites work @@
+Proof of the squashed cube conjecture
@@ Property / cites work: Proof of the squashed cube conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+$B$-valuations of graphs
@@ Property / cites work: $B$-valuations of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On Hamiltonian circuits and spanning trees of hypercubes
+Normal rank
@@ Property / cites work @@
+Q3041106
@@ Property / cites work: Q3041106 / rank @@
+Normal rank
@@ Property / cites work @@
+Embedding the dichotomic tree into the $n$-cube
@@ Property / cites work: Embedding the dichotomic tree into the $n$-cube / rank @@
+Normal rank
@@ Property / cites work @@
+Embedding the polytomic tree into the $n$-cube
@@ Property / cites work: Embedding the polytomic tree into the $n$-cube / rank @@
+Normal rank
@@ Property / cites work @@
+One-legged caterpillars span hypercubes
@@ Property / cites work: One-legged caterpillars span hypercubes / rank @@
+Normal rank
@@ Property / cites work @@
+On cubes and dichotomic trees
@@ Property / cites work: On cubes and dichotomic trees / rank @@
+Normal rank
@@ Property / cites work @@
+On quasistars in $n$-cubes
@@ Property / cites work: On quasistars in $n$-cubes / rank @@
+Normal rank
@@ Property / cites work @@
+The starlike trees which span a hypercube
@@ Property / cites work: The starlike trees which span a hypercube / rank @@
+Normal rank
@@ Property / cites work @@
+Smallest maximal matchings in the graph of the d-dimensional cube
+Normal rank