Complexity of products of even cycles

MaRDI QIDQ2908703zbMATH OpenFDO

Authors Paul C. Kainen

Publication date 5 September 2012

Published in Bulletin of the Institute of Combinatorics and its Applications (Search for Journal in Brave)

zbMATH Keywords

average crossig numbercartesian productmatching book thicknessouterplanar crossing numbrer and skewness

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) Graph operations (line graphs, products, etc.) (05C76)

Review text

Drawings of the Cartesian product \(C_r \times C_s\) of cycles or length \(r\) and \(s\) are considered. It is shown that the \textit{outerplanar crossing number} \(\nu_1(C_r \times C_s) \leq 4r^3 + 6r^2 - 8r\). The \textit{matching book thickness} \(\text{mbt}(G)\) is the minimum number of colors in an edge coloring of a layout of \(G\) such that same colored edges do not cross or are incident. It is shown that \(\text{mbt}(C_r \times C_s) = 4\) if both \(r\) and \(s\) are even and is \(5\) if precisely one of \(r\) or \(s\) is odd.

Recommendations

• scientific article; zbMATH DE number 7478527
• scientific article; zbMATH DE number 1156616
• Drawings of \(C_m\times C_n\) with one disjoint family. II
• The crossing numbers of products of cycles with 6-vertex trees
• On the crossing numbers of \(K_m\square C_n\) and \(K_{m,l}\square P_n\)

Cited in

(11)

• On the identification problems in products of cycles
• On dispersability of some products of cycles
• A survey on book-embedding of planar graphs
• scientific article; zbMATH DE number 3889772 (Why is no real title available?)
• Matching book thickness of generalized Petersen graphs
• On the dispersability of odd toroidal grids
• The matching book embeddings of pseudo-Halin graphs
• The dispersability of the Kronecker cover of the product of complete graphs and cycles
• On dispersability of some circulant graphs
• All bipartite circulants are dispersable
• The matching book embedding under some graph operations

This page was built for publication: Complexity of products of even cycles

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