#### Campus Units

Mathematics, Electrical and Computer Engineering

#### Document Type

Article

#### Publication Version

Accepted Manuscript

#### Publication Date

4-2017

#### Journal or Book Title

Journal of Graph Theory

#### Volume

84

#### Issue

4

#### First Page

552

#### Last Page

565

#### DOI

10.1002/jgt.22041

#### 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)

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) 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.

#### Copyright Owner

Wiley Periodicals, Inc.

#### Copyright Date

2016

#### Language

en

#### File Format

application/pdf

#### Recommended Citation

Gethner, Ellen; Hogben, Leslie; Lidicky, Bernard; Pfender, Florian; Ruiz, Amanda; and Young, Michael, "On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs" (2017). *Mathematics Publications*. 54.

https://lib.dr.iastate.edu/math_pubs/54

## Comments

This is the peer-reviewed version of the following article: Gethner, Ellen, Leslie Hogben, Bernard Lidický, Florian Pfender, Amanda Ruiz, and Michael Young. "On crossing numbers of complete tripartite and balanced complete multipartite graphs."

Journal of Graph Theory84, no. 4 (2017): 552-565, which has been published in final form at DOI: 10.1002/jgt.22041. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving.