{"id":5839,"date":"2026-03-04T09:11:13","date_gmt":"2026-03-04T01:11:13","guid":{"rendered":"https:\/\/transactions.nast.ph\/?p=5839"},"modified":"2026-03-28T17:39:30","modified_gmt":"2026-03-28T09:39:30","slug":"effects-of-subdivision-and-contraction-of-edges-on-the-dimension-of-a-graph","status":"publish","type":"post","link":"https:\/\/transactions.nast.ph\/?p=5839","title":{"rendered":"Effects of Subdivision and Contraction of Edges on the Dimension of a Graph"},"content":{"rendered":"\n<p class=\"has-text-align-center\">Severino V. Gervacio<br>Department of Mathematics, De La Salle University<\/p>\n\n\n\n<p class=\"has-text-align-center\"><a href=\"http:\/\/doi.org\/10.57043\/transnastphl.1998.5839\" data-type=\"link\" data-id=\"doi.org\/10.57043\/transnastphl.1998.5839\">doi.org\/10.57043\/transnastphl.1998.5839<\/a><\/p>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-1 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:66.66%\">\n<p><strong>Abstract<\/strong><\/p>\n\n\n\n<p>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&#8217;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\u2212n edges. Most results are proven by actual construction.<\/p>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:33.33%\">\n<h5 class=\"wp-block-heading\">Keywords<\/h5>\n\n\n<div class=\"taxonomy-post_tag wp-block-post-terms\"><a href=\"https:\/\/transactions.nast.ph\/?tag=dimension\" rel=\"tag\">dimension<\/a><span class=\"wp-block-post-terms__separator\">, <\/span><a href=\"https:\/\/transactions.nast.ph\/?tag=distance\" rel=\"tag\">distance<\/a><span class=\"wp-block-post-terms__separator\">, <\/span><a href=\"https:\/\/transactions.nast.ph\/?tag=edge-contraction\" rel=\"tag\">edge contraction<\/a><span class=\"wp-block-post-terms__separator\">, <\/span><a href=\"https:\/\/transactions.nast.ph\/?tag=edge-subdivision\" rel=\"tag\">edge subdivision<\/a><span class=\"wp-block-post-terms__separator\">, <\/span><a href=\"https:\/\/transactions.nast.ph\/?tag=euclidian-space\" rel=\"tag\">Euclidian space<\/a><span class=\"wp-block-post-terms__separator\">, <\/span><a href=\"https:\/\/transactions.nast.ph\/?tag=graph\" rel=\"tag\">graph<\/a><span class=\"wp-block-post-terms__separator\">, <\/span><a href=\"https:\/\/transactions.nast.ph\/?tag=hamillonian\" rel=\"tag\">Hamillonian<\/a><\/div><\/div>\n<\/div>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\"  class=\"wp-block-file__embed\" data=\"https:\/\/transactions.nast.ph\/wp-content\/uploads\/2026\/03\/TNP-1998-20_27_Effects-of-Subdivision-and-Contraction-of-Edges-on-the-Dimension-of-a-Graph.pdf\" type=\"application\/pdf\" style=\"width:100%;height:1090px\" aria-label=\"Embed of TNP 1998 (20)_27_Effects of Subdivision and Contraction of Edges on the Dimension of a Graph.\"><\/object><a id=\"wp-block-file--media-a8817283-8685-47e0-9de4-7c3b36dc7916\" href=\"https:\/\/transactions.nast.ph\/wp-content\/uploads\/2026\/03\/TNP-1998-20_27_Effects-of-Subdivision-and-Contraction-of-Edges-on-the-Dimension-of-a-Graph.pdf\">TNP 1998 (20)_27_Effects of Subdivision and Contraction of Edges on the Dimension of a Graph<\/a><a href=\"https:\/\/transactions.nast.ph\/wp-content\/uploads\/2026\/03\/TNP-1998-20_27_Effects-of-Subdivision-and-Contraction-of-Edges-on-the-Dimension-of-a-Graph.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-a8817283-8685-47e0-9de4-7c3b36dc7916\">Download<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Severino V. Gervacio<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[831],"tags":[1070,1072,1073,1071,1069,1068,1074],"class_list":{"0":"post-5839","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-1998-technical-papers","7":"tag-dimension","8":"tag-distance","9":"tag-edge-contraction","10":"tag-edge-subdivision","11":"tag-euclidian-space","12":"tag-graph","13":"tag-hamillonian","14":"czr-hentry"},"_links":{"self":[{"href":"https:\/\/transactions.nast.ph\/index.php?rest_route=\/wp\/v2\/posts\/5839"}],"collection":[{"href":"https:\/\/transactions.nast.ph\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/transactions.nast.ph\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/transactions.nast.ph\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/transactions.nast.ph\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5839"}],"version-history":[{"count":3,"href":"https:\/\/transactions.nast.ph\/index.php?rest_route=\/wp\/v2\/posts\/5839\/revisions"}],"predecessor-version":[{"id":6159,"href":"https:\/\/transactions.nast.ph\/index.php?rest_route=\/wp\/v2\/posts\/5839\/revisions\/6159"}],"wp:attachment":[{"href":"https:\/\/transactions.nast.ph\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5839"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/transactions.nast.ph\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5839"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/transactions.nast.ph\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5839"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}