The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000241 Crossing number of complete graph with n nodes.
(Formerly M2772 N1115)
0, 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150 (list; graph; refs; listen; history; text; internal format)



It was conjectured by A. Hill in 1958 (see Guy 1960 and Harary-Hill 1963) that a(n) = floor(n/2)*floor((n-1)/2)*floor((n-2)/2)*floor((n-3)/2)/4 (see A028723). This is also sometimes referred to as Guy's conjecture. - N. J. A. Sloane, Jan 21 2015

Verified for n = 11, 12 by Shengjun Pan and R. Bruce Richter, in "The Crossing Number of K_11 is 100", J. Graph Theory 56 (2) (2007) 128-134.

Also the sum of the dimensions of the irreducible representations of su(3) that first occur in the (n-5)-th tensor power of the tautological representation. - James Dolan (jdolan(AT)math.ucr.edu), Jun 02 2003

From Paul Barry, Oct 02 2008: (Start)

Another version of the conjecture is that a(n)=C(floor(n/2),2)*C(floor((n-1)/2),2).

We conjecture that this sequence is also given by one half of the third coefficient of the denominator polynomial of the n-th convergent to the g.f. of n!.


From the Lackenby reference: "One of the most basic questions in knot theory remains unresolved: is crossing number additive under connected sum? In other words, does the equality c(K1#K2) = c(K1) + c(K2) always hold, where c(K) denotes the crossing number of a knot K and K1#K2 is the connected sum of two (oriented) knots K1 and K2? Theorem 1.1. Let K1, . . .,Kn be oriented knots in the 3-sphere. Then (c(K1) + . . . + c(Kn)) / 152 <= c(K1# . . . #Kn) <= c(K1) + . . . + c(Kn)." - Jonathan Vos Post, Aug 26 2009

From the Pan and Richter reference: 0.8594 Z(n) <= a(n) <= Z(n), where Z(n) is the conjectured formula (Richter and Thomassen 1997, de Klerk et al. 2007). - Danny Rorabaugh, Mar 12 2015

a(n) <= A028723(n) for n = 13-21, 23, 25, 27, and 29 based on crossing numbers equal to A028723(n) found using QuickCross. - Eric W. Weisstein, May 02 2019


Ábrego, Bernardo M.; Aichholzer, Oswin; Fernández-Merchant, Silvia; Ramos, Pedro; Salazar, Gelasio. The 2-Page Crossing Number of K_n. Discrete Comput. Geom. 49 (2013), no. 4, 747-777. MR3068573

E. de Klerk, D. V. Pasechnik, and A. Schrijver, "Reduction of Symmetric Semidefinite Programs Using the Regular *-Representation." Math Program. 109 (2007) 613-624.

Jean-Paul Delahaye, in Pour La Science, Feb. 2013, #424, Logique et Calcul. Le problème de la fabrique de briques. (The problem of the brick factory), in French.

R. K. Guy, The crossing number of the complete graph, Bull. Malayan Math. Soc., Vol. 7, pp. 68-72, 1960.

Harary, Frank, and Anthony Hill. "On the number of crossings in a complete graph." Proceedings of the Edinburgh Mathematical Society (Series 2) 13.04 (1963): 333-338.

T. L. Saaty, The number of intersections in complete graphs, Engrg. Cybernetics 9 (1971), no. 6, 1102-1104 (1972).; translated from Izv. Akad. Nauk SSSR Tehn. Kibernet. 1971, no. 6, 151-154 (Russian). Math. Rev. 58 #21749.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

C. Thomassen, Embeddings and minors, pp. 301-349 of R. L. Graham et al., eds., Handbook of Combinatorics, MIT Press.


Table of n, a(n) for n=0..12.

Balko, Martin, Radoslav Fulek, and Jan Kynčl. Crossing numbers and combinatorial characterization of monotone drawings of K_n, arXiv preprint arXiv:1312.3679 [math.CO], 2013.  Also Discrete Computat. Geom., 53 (2015), 107-143.

Drago Bokal, Gasper Fijavz and David R. Wood, The Minor Crossing Number of Graphs with an Excluded Minor, arXiv:math/0609707 [math.CO], 2006.

J. Dolan et al., su(3) and Zarankiewicz's conjecture

P. Erdős and R. K. Guy, Crossing Number Problems The American Mathematical Monthly, Vol. 80, No. 1. (1973), pp. 52-58.

Paul C. Kainen, On a problem of P. Erdős, J. Combinatorial Theory 51968 374--377. MR0231744 (38 #72)

Marc Lackenby, The crossing number of composite knots, arXiv:0805.4706 [math.GT], 2009. [From Jonathan Vos Post, Aug 26 2009].

D. McQuillan and R. B. Richter, A parity theorem for drawings of complete and bipartite graphs, Amer. Math. Monthly, 117 (2010), 267-273.

A. Owens, On the biplanar crossing number, IEEE Trans. Circuit Theory, 18 (1971), 277-280.

A. Owens, On the biplanar crossing number, IEEE Trans. Circuit Theory, 18 (1971), 277-280. [Annotated scanned copy]

Shengjun Pan and R. Bruce Richter, The Crossing Number of K_11 is 100, J. Graph Theory 56 (2) (2007) 128-134.

R. B. Richter and C. Thomassen, Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs, Amer. Math. Monthly 104 (1997) 131-137.

Thomas L. Saaty, On polynomials and crossing numbers of complete graphs, J. Combinatorial Theory Ser. A 10 (1971), 183--184. MR0291013 (45 #107)

T. L. Saaty, The Minimum Number Of Intersections In Complete Graphs, PNAS 1964 52 (3) 688-690.

Eric Weisstein's World of Mathematics, Complete Graph

Eric Weisstein's World of Mathematics, Graph Crossing Number

Eric Weisstein's World of Mathematics, Guy's Conjecture

Eric Weisstein's World of Mathematics, Zarankiewicz's Conjecture


a(n) ~ n^4/64 (Guy, Kainen).

Empirical g.f.: -x^5*(1+x+x^2)/(x+1)^3/(x-1)^5, which is the same as the conjectured formula of A. Hill. - Simon Plouffe, Feb 06 2013


It is conjectured that this sequence coincides with A028723.

Cf. A007333, A014540, A030179, A121021, A191928.

Sequence in context: A246695 A132920 A127645 * A028723 A213291 A264365

Adjacent sequences:  A000238 A000239 A000240 * A000242 A000243 A000244




N. J. A. Sloane


Bokal et al. link from Jonathan Vos Post, Dec 08 2006

Entry revised by N. J. A. Sloane, Jan 21 2015

Conjectured data values deleted by Eric W. Weisstein, May 01 2019



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 28 23:44 EST 2020. Contains 338755 sequences. (Running on oeis4.)