Severino V. Gervacio
Department of Mathematics, De La Salle University
doi.org/10.57043/transnastphl.1998.5839
Abstract
If the vertices of a graph can be associated bijectively with points in the n-dimensional Euclidean space En such that the distance between points associated with adjacent vertices is unity, then the graph is called a unit graph in En. The smallest n for which a graph G is a unit graph in En is called the dimension of G. Harary, et al, sometime in the 60’s determined the dimension of some graphs and gave upper bounds for the dimension of a graph in terms of the number of vertices and in terms of the chromatic number. The effects of two graph operations on the dimension of a graph are considered here. An edge subdivision means inserting one new vertex in an edge of a graph. An edge contraction means reducing an edge to a single vertex by identifying its end vertices. Here, we show that the edge subdivision or edge contraction may either increase, decrease or leave the dimension of a graph unchanged. We prove here that every graph with n vertices and m edges can be subjected to a finite number of edge subdivisions to obtain a unit graph in E2 with n+m vertices and 2m edges. Likewise, a Hamiltonian graph with n vertices and m edges can be subjected to a finite number of edge subdivisions to yield a unit graph in E2 with m vertices and 2m−n edges. Most results are proven by actual construction.