On cubical graphs

AbstractIt is frequently of interest to represent a given graph G as a subgraph of a graph H which has some special structure. A particularly useful class of graphs in which to embed G is the class of n-dimensional cubes. This has found applications, for example, in coding theory, data transmission, and linguistics. In this note, we study the structure of those graphs G, called cubical graphs (not to be confused with cubic graphs, those graphs for which all vertices have degree 3), which can be embedded into an n-dimensional cube. A basic technique used is the investigation of graphs which are critically nonembeddable, i.e., which can not be embedded but all of whose subgraphs can be embedded