✦ LIBER ✦

The crossing number of K11 is 100

✍ Scribed by Shengjun Pan; R. Bruce Richter

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 121 KB
Volume: 56
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20249

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The crossing number of K~n~ is known for n ⩽ 10. We develop several simple counting properties that we shall exploit in showing by computer that cr(K~11~ = 100, which implies that cr(K~12~) = 150. We also determine the numbers of non‐isomorphic optimal drawings of K~9~ and K~10~. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 128–134, 2007

📜 SIMILAR VOLUMES

The crossing number of K1,3,n and K2,3,n

✍ Kouhei Asano 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 234 KB

In this article, we will determine the crossing number of the complete tripartite graphs K,.3.n and K2,3.n. Our proof depends on Kleitman's results for the complete bipartite graphs [D. J. Kleitman, The crossing number of K5,n. J. Combhatorial Theory 9 (1970) 375-3231. a graph G is the minimum numbe

The crossing number of c4 × c4

✍ Alice M. Dean; R. Bruce Richter 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

We prove t h a t t h e crossing number of C4 X Ca is 8.

An improvement of the crossing number bo

An improvement of the crossing number bound

✍ Bernard Montaron 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

## Abstract The crossing number __cr__(__G__) of a simple graph __G__ with __n__ vertices and __m__ edges is the minimum number of edge crossings over all drawings of __G__ on the ℝ^2^ plane. The conjecture made by Erdős in 1973 that __cr__(__G__) ≥ __Cm__^3^/__n__^2^ was proved in 1982 by Leighton

The book crossing number of a graph

✍ Shahrokhi, Farhad; Sz�kely, L�szl� A.; S�kora, Ondrej; Vrt'o, Imrich 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 581 KB

Let G be a graph on n vertices and m edges. The book crossing number of G is defined as the minimum number of edge crossings when the vertices of G are placed on the spine of a k-page book and edges are drawn on pages, such that each edge is contained by one page. Our main results are t w o polynomi

The crossing number of Cm × Cn is as con

The crossing number of Cm × Cn is as conjectured for n ≥ m(m + 1)

✍ Lev Yu. Glebsky; Gelasio Salazar 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract It has been long conjectured that the crossing number of __C~m~__ × __C~n~__ is (__m__−2)__n__, for all __m__, __n__ such that __n__ ≥ __m__ ≥ 3. In this paper, it is shown that if __n__ ≥ __m__(__m__ + 1) and __m__ ≥ 3, then this conjecture holds. That is, the crossing number of __

Bounding the crossing number of a graph

Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree

✍ Enrique Garcia-Moreno; Gelasio Salazar 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB 👁 3 views