Subdividing a Graph Toward a Unit-distance Graph in the Plane

Authors: Gervacio S.V.¹; Maehara H.²

Source: European Journal of Combinatorics, Volume 21, Number 2, February 2000 , pp. 223-229(7)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

The subdivision number of a graph 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. Lett(n) denote the maximum number of edges of a C₄-free graph on n vertices. It is proved that the subdivision number of K_nlies betweenn(n - 1) / 2 - t(n)and (n - 2)(n - 3) / 2 + 2, and that of K(m, n) equals (m - 1)(n - m) forn m(m - 1). Copyright 2000 Academic Press

Language: English

Document Type: Research article

Affiliations: 1: Mathematics Department, De La Salle University, Taft Avenue, Manila 1004, 2401, Philippines 2: College of Education, Ryukyu University, Nishihara, Okinawa 903–0213, Japan

Publication date: 2000-02-01