Constructing unit-distance graphs by subdividing edges

Date of Publication

2002

Document Type

Master's Thesis

Degree Name

Master of Science in Mathematics

Subject Categories

Numerical Analysis and Computation

College

College of Science

Department/Unit

Mathematics and Statistics

Thesis Adviser

Severino V. Gervacio

Defense Panel Chair

Blessilda P. Raposa

Defense Panel Member

Erminda C. Fortez
Isagani Jos

Abstract/Summary

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].

Abstract Format

html

Language

English

Format

Print

Accession Number

TG03237

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

122 leaves ; 28 cm.

Keywords

Graphic methods; Graph theory; Representations of graphs

Upload Full Text

wf_no

This document is currently not available here.

Share

COinS