The crossing numbers of Cartesian product of cone graph C_m+K_l with path P_n.

MaRDI QIDQ2881277zbMATH OpenFDO

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

Publication date 3 April 2012

Published in Ars Combinatoria (Search for Journal in Brave)

zbMATH Keywords

crossing numberscyclepathproduct of graphswheel

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Review text

A crossing number \(cr(G)\) of a graph \(G\) is the minimal number of crossings in any drawing of the graph in the plane. The authors study the crossing number of a particular family of graphs: Let \(W_{l,m}\) be the graph obtained from \(C_m\) by adding \(l\) vertices connected to every vertex of the cycle and let \(\square \) denote the cartesian product. The authors show that NEWLINENEWLINE\[NEWLINE\begin{multlined}NEWLINEcr(W_{l,m}\square P_n) \leq NEWLINE(n-1) \left( \left\lfloor {\frac {l+2}{2}} \right\rfloor \left\lfloor {\frac {l+1}{2}} \right\rfloor \left\lfloor {\frac {m+2}{2}} \right\rfloor \left\lfloor {\frac {m+1}{2}}\right\rfloor -lm + l \right) +\\NEWLINE+2\left( \left\lfloor {\frac {l}{2}} \right\rfloor \left\lfloor {\frac {l+1}{2}} \right\rfloor \left\lfloor {\frac {m}{2}} \right\rfloor \left\lfloor {\frac {m+1}{2}}\right\rfloor - \left\lfloor {\frac {l}{2}} \right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor + \left\lfloor {\frac {l+1}{2}}\right\rfloor \right).NEWLINE\end{multlined}NEWLINE\]NEWLINENEWLINEAs a main result they show equality in this bound for \(l=1\) and \(l=2\). They conjecture that equality hold for every values of \(l\), \(m\), and \(n\).

Recommendations

• The crossing numbers of Cartesian products of path with some graphs.
• The crossing number of Cartesian products of complete bipartite graphs \(K_{2,m}\) with paths \(P_{n}\)
• The crossing number of the Cartesian product of paths with complete graphs
• scientific article; zbMATH DE number 3954951
• scientific article; zbMATH DE number 2073946
• The crossing number of Cartesian product of P_n with circulant graph C(10,2)
• On the crossing numbers of Cartesian products of paths with special graphs
• scientific article; zbMATH DE number 5732461
• On the crossing numbers of Cartesian products with paths
• The crossing number of Cartesian product of circulant graph C(9,2) with path P_n

Cited in

(10)

• A note on the crossing number of the cone of a graph
• The crossing number of Cartesian product of circulant graph C(9,2) with path P_n
• The crossing number of the cone of a graph
• The crossing numbers of the direct product of \({K_m}\) and \({P_n}\)
• The crossing number of the cone of a graph
• On the crossing numbers of join products of \(W_4+P_n\) and \(W_4+C_n\)
• A survey of graphs with known or bounded crossing numbers
• The crossing number of Cartesian product of sunlet graph with path and complete bipartite graph
• On the crossing numbers of Cartesian products with paths
• On the crossing numbers of \(K_m\square C_n\) and \(K_{m,l}\square P_n\)

This page was built for publication: The crossing numbers of Cartesian product of cone graph \(C_{m}+K_l\) with path \(P_{n}\).

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