CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCMB
Publications        
Abstract view

The Thickness of the Cartesian Product of Two Graphs

  Published:2016-05-10
 Printed: Dec 2016
  • Yichao Chen,
    Department of Mathematics, Hunan University, 410082 Changsha, China
  • Xuluo Yin,
    Department of Mathematics, Hunan University, 410082 Changsha, China
Format:   LaTeX   MathJax   PDF  

Abstract

The thickness of a graph $G$ is the minimum number of planar subgraphs whose union is $G.$ A $t$-minimal graph is a graph of thickness $t$ which contains no proper subgraph of thickness $t.$ In this paper, upper and lower bounds are obtained for the thickness, $t(G\Box H)$, of the Cartesian product of two graphs $G$ and $H$, in terms of the thickness $t(G)$ and $t(H)$. Furthermore, the thickness of the Cartesian product of two planar graphs and of a $t$-minimal graph and a planar graph are determined. By using a new planar decomposition of the complete bipartite graph $K_{4k,4k},$ the thickness of the Cartesian product of two complete bipartite graphs $K_{n,n}$ and $K_{n,n}$ is also given, for $n\neq 4k+1$.
Keywords: planar graph, thickness, Cartesian product, $t$-minimal graph, complete bipartite graph planar graph, thickness, Cartesian product, $t$-minimal graph, complete bipartite graph
MSC Classifications: 05C10 show english descriptions Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25] 05C10 - Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25]
 

© Canadian Mathematical Society, 2017 : https://cms.math.ca/