| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
[2] Univ Autonoma San Luis Potosi, Inst Fis, San Luis Potosi - Mexico
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | ELECTRONIC JOURNAL OF COMBINATORICS; v. 21, n. 4 OCT 2 2014. |
| Web of Science Citations: | 2 |
| Abstract | |
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) | |
| FAPESP's process: | 12/24597-3 - Topological and structural problems in graph theory. |
| Grantee: | César Israel Hernández Vélez |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |