On cubical graphs |
| |
Authors: | MR Garey RL Graham |
| |
Institution: | Bell Laboratories, Murray Hill, New Jersey 07974 USA |
| |
Abstract: | It 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|