The optimal drawings of K₅,n

MaRDI QIDQ463036zbMATH OpenFDO

Authors César Hernández-Vélez, Carolina Medina, Gelasio Salazar

Publication date 23 October 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.1988, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p1

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

antipodal verticescrossing numbersoptimal drawingsZarankiewicz conjectureTurán's brickyard problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Zarankiewicz's Conjecture (ZC) states that the crossing number cr$(K_{m,n})$ equals $Z(m,n):=floorfracm2floorfracm-12floorfracn2floorfracn-12$. Since Kleitman's verification of ZC for $K_{5,n}$ (from which ZC for $K_{6,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,n}$. The widely known natural drawings of $K_{m,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,2}$ has no crossings. Antipodal vertices also play a major role in Kleitman's inductive proof that cr$(K_{5,n})=Z(5,n)$. We explore in depth the role of antipodal vertices in optimal drawings of $K_{5,n}$, for $n$ even. We prove that if {$nequiv2$ (mod 4)}, then every optimal drawing of $K_{5,n}$ has antipodal vertices. We also exhibit a two-parameter family of optimal drawings $D_{r,s}$ of $K_{5,4(r+s)}$ (for $r,sge0$), with no antipodal vertices, and show that if $nequiv0$ (mod 4), then every optimal drawing of $K_{5,n}$ without antipodal vertices is (vertex rotation) isomorphic to $D_{r,s}$ for some integers $r,s$. As a corollary, we show that if $n$ is even, then every optimal drawing of $K_{5,n}$ is the superimposition of Zarankiewicz drawings with a drawing isomorphic to $D_{r,s}$ for some nonnegative integers $r,s$.

Recommendations

• scientific article; zbMATH DE number 2114468
• Packing of \(K_{v}\) with certain graphs of five vertices
• Drawing \(K_{2,n}\): A lower bound
• Geometric drawings of \(K_{n}\) with few crossings
• scientific article; zbMATH DE number 219263
• A (5,5)-Colouring of K_n with Few Colours
• Maximizing five-cycles in \(K_r\)-free graphs
• Five-coloring graphs on the Klein bottle
• A note to maximum packings of \(K_v\) with a graph \(G\) of five vertices and five edges
• K₅-Subdivisions in Graphs

Cites work

• scientific article; zbMATH DE number 3306563 (Why is no real title available?)
• Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• Improved lower bounds for the 2-page crossing numbers of \(K_{m,n}\) and \(K_n\) via semidefinite programming
• On a problem of P. Turan concerning graphs
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• The crossing number of K5,n
• Zarankiewicz's conjecture is finite for each fixed \(m\)

Cited in

(15)

• On the crossing numbers of join products of four graphs of order six with the discrete graph
• Cyclic permutations in determining crossing numbers
• Determining crossing number of join of the discrete graph with two symmetric graphs of order five
• The crossing numbers of join of special disconnected graph on five vertices with discrete graphs
• DETERMINING CROSSING NUMBERS OF GRAPHS OF ORDER SIX USING CYCLIC PERMUTATIONS
• The crossing numbers of join products of paths with three graphs of order five
• On the crossing number of join product of the discrete graph with special graphs of order five
• Drawing \(K_{2,n}\): A lower bound
• The crossing numbers of join product of four graphs on six vertices with discrete graphs
• On the crossing numbers of join products of \(W_4+P_n\) and \(W_4+C_n\)
• The crossing numbers of join products of four graphs of order five with paths and cycles
• Determining crossing numbers of the join products of two specific graphs of order six with the discrete graph
• On the crossing number of the join of the wheel on five vertices with the discrete graph
• On the crossing numbers of join products of five graphs of order six with the discrete graph
• The influence of separating cycles in drawings of \(K_5 \setminus e\) in the join product with paths and cycles

This page was built for publication: The optimal drawings of \(K_{5,n}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463036)