The coordinate representation of a graph and n-universal graph of radius 1
Andrey A. Ivashchenko · Discrete Mathematics · 1993
Every graph can be represented as the intersection graph on a family of closed unit cubes in Euclidean space En. Cube vertices have integer coordinates. The coordinate matrix, A(G)={vnk} of a graph G is defined by the set of cube coordinates. The imbedded dimension of a graph, Bp(G), is a number of columns in matrix A(G) such that each of them has at least two distinct elements vnk≠vpk. We show that Bp(G)=cub(G) for some graphs, and Bp(G)⩽n−2 for any graph G on n vertices. The coordinate matrix uses to obtain the graph U of radius 1 with 3n−2 vertices that contains as an induced subgraph a copy of any graph on n vertices.