The optimal drawings of K-5,K-n

Autor(es)

Hernandez-Velez, Cesar ^[1] ; Medina, Carolina ^[2] ; Salazar, Gelasio ^[2]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil

^[2] Univ Autonoma San Luis Potosi, Inst Fis, San Luis Potosi - Mexico

• Tipo de documento: Artigo Científico
• Fonte: ELECTRONIC JOURNAL OF COMBINATORICS; v. 21, n. 4 OCT 2 2014.
• Citações Web of Science: 2

Resumo

Zarankiewicz's Conjecture (ZC) states that the crossing number cr(K-m,K-n) equals Z(m, n) := {[}m/2] {[}m-1/2] {[}n/2] {[}n-1/2]. Since Kleitman's verification of ZC for K-5,K-n (from which ZC for K-6,K-n easily follows), very little progress has been made around ZC; the most notable exceptions involve computer-aided results. With the aim of gaining a more profound understanding of this notoriously difficult conjecture, we investigate the optimal (that is, crossing-minimal) drawings of K-5,K-n. The widely known natural drawings of K-m,K-n (the so-called Zarankiewicz drawings) with Z(m,n) crossings contain antipodal vertices, that is, pairs of degree-m vertices such that their induced drawing of K-m,K-2 has no crossings. Antipodal vertices also play a major role in Kleitman's inductive proof that cr(K-5,K-n) = Z((5,n)). We explore in depth the role of antipodal vertices in optimal drawings of K-5,K-n, for n even. We prove that if n equivalent to 2 (mod 4), then every optimal drawing of K-5,K-n has antipodal vertices. We also exhibit a two-parameter family of optimal drawings D-r,D-s of K-5,K-4(r+ s) (for r,s >= 0), with no antipodal vertices, and show that if n equivalent to 0 (mod 4), then every optimal drawing of K-5,K-n without antipodal vertices is (vertex rotation) isomorphic to D-r,D-s for some integers r,s. As a corollary, we show that if n is even, then every optimal drawing of K-5,K-n is the superimposition of Zarankiewicz drawings with a drawing isomorphic to D-r,D-s for some nonnegative integers r, s. (AU)

• Processo FAPESP: 12/24597-3 - Problemas topológicos e estruturais em teoria dos grafos.
• Beneficiário: César Israel Hernández Vélez
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado