Subdivision number of large complete graphs and large complete multipartite graphs

College

College of Science

Department/Unit

Mathematics and Statistics Department

Document Type

Conference Proceeding

Source Title

Lecture Notes in Computer Science

Volume

3330

First Page

94

Last Page

101

Publication Date

1-1-2005

Abstract

A graph whose vertices can be represented by distinct points in the plane such that points representing adjacent vertices are 1 unit apart is called a unit-distance graph. Not all graphs are unit distance graphs. However, if every edge of a graph is subdivided by inserting a new vertex, then the resulting graph is a unit-distance graph. The minimum number of new vertices to be inserted in the edges of a graph G to obtain a unit-distance graph is called the subdivision number of G, denoted by sd (G). We show here in a different and easier way the known result sd(Km,n) = (m - 1)(n - m) when n ≥ m(m - 1). This result is used to show that the subdivision number of the complete graph is asymptotic to (2n), its number of edges. Likewise, the subdivision number of the complete bipartite graph Km,n is asymptotic to mn, its number of edges. More generally, the subdivision number of the complete n-partite graph is asymptotic to its number of edges. © Springer-Verlag Berlin Heidelberg 2005.

html

Digitial Object Identifier (DOI)

10.1007/978-3-540-30540-8_10

Disciplines

Mathematics

Keywords

Bipartite graphs; Graph theory

Upload File

wf_yes

This document is currently not available here.

Share

COinS