Cubical graphs and cubical dimensions

DOI10.1016/0898-1221(88)90212-XMaRDI QIDQ1102987zbMATH OpenOpenAlexFDO

Authors Frank Harary

Publication date 1988

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(88)90212-x

zbMATH Keywords

cubical dimensioncubical graph

Mathematics Subject Classification ID

Polyominoes (05B50) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Review text

A cubical graph G is isomorphic to a subgraph of some hypercube \(Q_ n\). The cubical dimension cd(G) is the smallest such n. The induced cubical dimension icd(G) is the minimum n for which G is an induced subgraph of \(Q_ n\). The determination for a given cubical graph G of the exact values of cd(G) and icd(G) is very difficult. We discuss these values for some special classes of graphs including trees, unicyclic graphs, ``polyomino animals and polyhexes.

Recommendations

• The complexity of cubical graphs
• scientific article; zbMATH DE number 3936535
• The cubicity of hypercube graphs
• scientific article; zbMATH DE number 125454
• On the cubicity of certain graphs

Cites work

• A survey of the theory of hypercube graphs
• Embedding the dichotomic tree into the n-cube
• On cubical graphs
• On Homeomorphic Embeddings of K_m,n in the Cube
• Parallel concepts in graph theory
• The enumeration of tree-like polyhexes

Cited in

(22)

• Spanning cubic graph designs
• Cubic graphs whose average number of regions is small
• Generalized sum graphs
• Cover-preserving order embeddings into Boolean lattices
• Cubic graphs and related triangulations on orientable surfaces
• Transformations of cubic graphs
• Orientation spectra of cubic graphs
• On semicube graphs
• Partial cubes and crossing graphs
• Permutation-exchange graphs that emulate the binary cube
• scientific article; zbMATH DE number 5844218 (Why is no real title available?)
• scientific article; zbMATH DE number 3936535 (Why is no real title available?)
• The complexity of cubical graphs
• scientific article; zbMATH DE number 4010537 (Why is no real title available?)
• An Explicit Construction of Lower-Diameter Cubic Graphs
• Cubic bridgeless graphs and braces
• Induced embeddings into Hamming graphs
• A note on the cubical dimension of new classes of binary trees.
• On the dimer problem of the vertex-edge graph of a cubic graph
• Distance regular subgraphs of a cube
• Boolean autoencoders and hypercube clustering complexity
• Graphs which are locally a cube

This page was built for publication: Cubical graphs and cubical dimensions

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