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 C-4-free graph on n vertices. It is proved that the subdivision number of K-n 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 greater than or equal to m(m - 1). (C) 2000 Academic Press. |
Year | DOI | Venue |
---|---|---|
2000 | 10.1006/eujc.1999.0348 | Eur. J. Comb. |
Keywords | Field | DocType |
unit-distance graph | Wheel graph,Discrete mathematics,Graph toughness,Combinatorics,Bound graph,Graph power,Cycle graph,Unit distance graph,Distance-regular graph,Mathematics,Path graph | Journal |
Volume | Issue | ISSN |
21 | 2 | 0195-6698 |
Citations | PageRank | References |
3 | 0.66 | 1 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Severino V. Gervacio | 1 | 22 | 6.38 |
Hiroshi Maehara | 2 | 152 | 114.17 |