Constructing unit-distance graphs by subdividing edges

• Main Author: Calayag, Ernita Rodriguez
• Format: text
• Language: English
• Published: Animo Repository 2002
• Subjects: Graphic methods; Graph theory; Representations of graphs; Numerical Analysis and Computation
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/2634
• Institution: De La Salle University

A subdivision of graph G, S(G), is the result of subdividing some edges of G. The subdivision number of a graph G denoted by sd(G) is defined to be the minimum number of extra vertices inserted into the edges of G to make it isomorphic to a unit-distance graph in the plane (R2). A unit-distance graph in R2 is a simple connected graph whose vertices can be represented by distinct points in the plane such that the euclidean distance between any pair of adjacent vertices is one. In the study, t(n) denotes the maximum number of edges of a graph without four-cycle on n vertices. The paper will show that the subdivision number of a complete graph Kn on n vertices lies between [[n(n-1)]/2]-t(n) and [(n-2)(n-3)/2]+2 and that of a complete bipartite graph Km, n equals (m-1)(n-m) for n greater than or equal to m(m-1).This thesis is an exposition of the paper entitled Subdividing a Graph Toward a Unit-distance Graph in the Plane by Dr. Severino V. Gervacio and Prof. Hiroshi Maehara published in the February 2000 issue of European Journal of Combinatorics, [9].