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 drawingsTurán's brickyard problemZarankiewicz conjecture

Mathematics Subject Classification ID

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

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$.

Review text

Summary: Zarankiewicz's Conjecture (ZC) states that the crossing number~cr\((K_{m,n})\) equals \(Z(m,n):=\lfloor{\frac{m}{2}}\rfloor\,\lfloor{\frac{m-1}{2}}\rfloor\,\lfloor{\frac{n}{2}}\rfloor\,\lfloor{\frac{n-1}{2}}\rfloor\). 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 \textit{optimal} (that is, crossing-minimal) drawings of \(K_{5,n}\). The widely known natural drawings of \(K_{m,n}\) (the so-called \textit{Zarankiewicz drawings}) with \(Z(m,n)\) crossings contain \textit{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 \(n \equiv 2\) (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,s\geq 0\)), with no antipodal vertices, and show that if \(n\equiv 0\) (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

• Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
• scientific article; zbMATH DE number 3306563 (Why is no real title available?)
• 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 -representation
• The crossing number of K5,n
• Zarankiewicz's conjecture is finite for each fixed \(m\)

Cited in

(19)

• Drawing \(K_{2,n}\): A lower bound
• 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
• Cyclic permutations in determining crossing numbers
• On the crossing numbers of join products of four graphs of order six with the discrete graph
• DETERMINING CROSSING NUMBERS OF GRAPHS OF ORDER SIX USING CYCLIC PERMUTATIONS
• On the crossing number of join product of the discrete graph with special graphs of order five
• On the crossing numbers of join products of \(W_4+P_n\) and \(W_4+C_n\)
• The crossing numbers of join products of paths with three graphs of order five
• On the crossing numbers of join products of five 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
• Determining crossing numbers of the join products of two specific graphs of order six with the discrete graph
• The crossing numbers of join products of four graphs of order five with paths and cycles
• The crossing numbers of join product of four graphs on six vertices with discrete graphs
• The influence of separating cycles in drawings of K₅ e in the join product with paths and cycles
• The crossing numbers of join products of K₄ K₁ with cycles
• Conjectures about wheels in the join product with cycles
• Conjectures about wheels without one edge
• The crossing numbers of join products of seven graphs of order six 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)