Subdividing a graph toward a unit-distance graph in the plane
College
College of Science
Department/Unit
Mathematics and Statistics Department
Document Type
Article
Source Title
European Journal of Combinatorics
Volume
21
First Page
223
Last Page
229
Publication Date
2020
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. Let t(n) denote the maximum number of edges of a C4-free graph on n vertices. It is proved that the subdivision number of Kn lies between n(n − 1)/2 − t(n) and (n − 2)(n − 3)/2 + 2, and that of K(m, n) equals (m − 1)(n − m) for n ≥ m(m − 1).
html
Digitial Object Identifier (DOI)
10.1006/eujc.1999.0348
Recommended Citation
Gervacio, S. V., & Maehara, H. (2020). Subdividing a graph toward a unit-distance graph in the plane. European Journal of Combinatorics, 21, 223-229. https://doi.org/10.1006/eujc.1999.0348
Disciplines
Mathematics
Keywords
Graph theory
Upload File
wf_no
