On the crossing numbers of K_m C_n and K_m,l P_n

DOI10.1016/J.DAM.2007.09.007MaRDI QIDQ944744zbMATH OpenOpenAlexFDO

Authors Zheng Wenping, Lin Xiaohui, Yuansheng Yang, Deng Chengrui

Publication date 10 September 2008

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2007.09.007

zbMATH Keywords

Cartesian productComplete bipartite graphComplete graphCrossing number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

Let \(G_1\square G_2\) be the Cartesian product of two graphs \(G_1\) and \(G_2\). \textit{R. D. Ringeisen} and \textit{L. W. Beineke} [J. Comb. Theory, Ser. B 24, 134--136 (1978; Zbl 0383.05015)] have proved that \(cr(C_3\square C_n)=n\) and \(cr(K_4\square C_n)=3n\). \textit{D. Bokal} [J. Comb. Theory, Ser. B 97, 381--384 (2007; Zbl 1113.05027)] has proved that \(cr(K_{1,l}\square P_n)=(n-1)\lfloor \frac l2\rfloor\lfloor\frac{l-1}2\rfloor\). In this paper the authors study the crossing numbers of \(K_m\square C_n\) and \(K_{m,l}\square P_n\), and show that {\parindent=7mm \begin{itemize}\item[(i)]\(cr(K_m\square C_n)\geq n\cdot cr(K_{m+2})\) for \(n\geq3\) and \(m\geq5\); \item[(ii)]\(cr(K_m\square C_n)\leq\frac n4\lfloor\frac{m+2}2\rfloor\lfloor\frac {m+1}2\rfloor\lfloor\frac m2\rfloor\lfloor\frac{m-1}2\rfloor\) for \(m=5,6,7\) and for \(m\geq8\) with even \(n\geq4\), and equality holds for \(m=5,6,7\) and for \(m=8,9,10\) with even \(n\geq4\) and \item[(iii)]\(cr(K_{m,l}\square P_n)\leq(n-1)(\lfloor\frac{m+2}2\rfloor\lfloor\frac{m+1}2\rfloor\lfloor\frac{l+2}2\rfloor\lfloor\frac{l+1}2\rfloor-ml)+2(\lfloor\frac{m+1}2\rfloor\lfloor\frac m2\rfloor\lfloor\frac{l+1}2\rfloor\lfloor\frac l2\rfloor-\lfloor\frac m2\rfloor\lfloor\frac l2\rfloor)\) for \(\min(m,l)\geq2\), and equality holds for \(\min(m,l)=2\). \end{itemize}}

Recommendations

• On the crossing number of \(K_{ m } \square P_{n}\)
• The crossing numbers of Cartesian product of cone graph \(C_{m}+K_l\) with path \(P_{n}\).
• <italic>K</italic><sub>1,1,<italic>m</italic></sub>□<italic>P</italic><sub><italic>n</italic>&l
• The crossing numbers of the direct product of \({K_m}\) and \({P_n}\)
• The crossing number of \(P^2_n \square C_3\)

Cites work

• Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
• scientific article; zbMATH DE number 3657692 (Why is no real title available?)
• scientific article; zbMATH DE number 90572 (Why is no real title available?)
• scientific article; zbMATH DE number 1156577 (Why is no real title available?)
• scientific article; zbMATH DE number 1536528 (Why is no real title available?)
• scientific article; zbMATH DE number 3803471 (Why is no real title available?)
• scientific article; zbMATH DE number 889956 (Why is no real title available?)
• On a problem of P. Turan concerning graphs
• On the crossing numbers of Cartesian products with paths
• On the crossing numbers of products of cycles and graphs of order four
• On the crossing numbers of products of stars and graphs of order five
• The crossing number of \(C_3\times C_n\)
• The crossing number of \(K_{2,m}\square P_n\)
• The crossing number of K5,n
• The crossing number ofK1,3,n andK2,3,n
• The crossing numbers of Cartesian products of paths with 5-vertex graphs
• The crossing numbers of certain Cartesian products
• The crossing numbers of products of paths and stars with 4‐vertex graphs

Cited in

(21)

• The crossing number of \(C(8,2)\square P_{n}\)
• Optimal meshes of curves in the Klein bottle
• The crossing number of locally twisted cubes \(L T Q_n\)
• The crossing number of the Cartesian product of paths with complete graphs
• Complexity of products of even cycles
• The crossing number of Cartesian product of P_n with circulant graph C(10,2)
• The crossing numbers of the direct product of \({K_m}\) and \({P_n}\)
• The crossing number ofCm �Cn is as conjectured forn ?m(m + 1)
• scientific article; zbMATH DE number 5952049 (Why is no real title available?)
• scientific article; zbMATH DE number 3954951 (Why is no real title available?)
• scientific article; zbMATH DE number 4123124 (Why is no real title available?)
• On k-crossings and k-nestings of permutations
• Crossing number of Cartesian product of prism and path
• On the crossing number of the Cartesian product of a sunlet graph and a star graph
• On the Cartesian products with crossing number three
• <italic>K</italic><sub>1,1,<italic>m</italic></sub>□<italic>P</italic><sub><italic>n</italic></sub> 的交叉数
• A survey of graphs with known or bounded crossing numbers
• On the crossing numbers of Cartesian products of wheels and trees
• scientific article; zbMATH DE number 5238993 (Why is no real title available?)
• On the crossing number of \(K_{ m } \square P_{n}\)
• The crossing number of \(K_{2,m}\square P_n\)

This page was built for publication: On the crossing numbers of \(K_m\square C_n\) and \(K_{m,l}\square P_n\)

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