Name
Title | ||
|---|---|---|
On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs. |
Abstract | ||
|---|---|---|
The crossing number cr(G) of a graph G is the minimum number of crossings in a drawing of G in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number (cr) over bar (G) of G is the minimum number of crossings in a such drawing of G with edges as straight line segments. Zarankiewicz proved in 1952 that (cr) over bar (K-n1,K- n2) <= Z(n(1), n(2)) := left perpendicular n(1)/2 right perpendicular left perpendicular n(1)-1/2 right perpendicular left perpendicular n(2)/2 right perpendicular left perpendicular n(2)-1/2 right perpendicular. We generalize the upper bound Z(n(1), n(2)) to A(n1, n2, n3) := [GRAPHICS] (left perpendicular n(j)/2 right perpendicular left perpendicular n(j)-1/2 right perpendicular left perpendicular n(k)/2 right perpendicular left perpendicular n(k)-1/2 right perpendicular + left perpendicular n(i)/2 right perpendicular left perpendicular n(i)-1/2 right perpendicular left perpendicular n(j)n(k)/2 right perpendicular), and prove (cr) over bar (K-n1,K- n2,K- n3) <= A(n1, n2, n3). We also show that for n large enough, 0.973A(n, n, n) <= (cr) over bar (K-n,K- n,K- n) and 0.666A(n, n, n) <= (cr) over bar (K-n,K- n,K- n), with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph is balanced if the partite sets all have the same cardinality. We study asymptotic behavior of the crossing number of the balanced complete r- partite graph. Richter and Thomassen proved in 1997 that the limit as n -> infinity of cr(K-n,K- n) over the maximum number of crossings in a drawing of K-n,K- n exists and is at most 1/4. We define zeta(r) := 3(r(2) - r)/8(r(2) + r-3) and show that for a fixed r and the balanced complete r- partite graph, zeta(r) is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing. (C) 2016 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1002/jgt.22041 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
crossing number,rectilinear crossing number,complete tripartite graph,complete multipartite graph,balanced,flag algebra | Topology,Discrete mathematics,Combinatorics,Outerplanar graph,Crossing number (graph theory),Slope number,Graph power,Toroidal graph,Book embedding,Graph minor,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
84.0 | 4.0 | 0364-9024 |
Citations | PageRank | References |
4 | 0.43 | 7 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ellen Gethner | 1 | 66 | 12.55 |
| Leslie Hogben | 2 | 113 | 14.58 |
| Bernard Lidický | 3 | 9 | 5.00 |
| Florian Pfender | 4 | 285 | 30.96 |
| Amanda Ruiz | 5 | 4 | 0.77 |
| Michael Young | 6 | 6 | 2.59 |