Name
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 ($n \above 0pt 2$), 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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-30540-8_10 | IJCCGGT |
Keywords | Field | DocType |
complete graph,complete n-partite graph,subdivision number,unit-distance graph,large complete multipartite graph,new vertex,large complete graph,graph g,minimum number,unit distance graph,resulting graph,complete bipartite graph | Discrete mathematics,Combinatorics,Outerplanar graph,Line graph,Crossing number (graph theory),Forbidden graph characterization,Graph power,Cycle graph,Planar graph,Mathematics,Complement graph | Conference |
ISBN | Citations | PageRank |
3-540-24401-8 | 0 | 0.34 |
References | Authors | |
2 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Severino V. Gervacio | 1 | 22 | 6.38 |