完全二部图Kn+1,2n与完全三部图K1,n,2n的厚度关系

The Relationship Between the Thickness of the Complete Bipartite Graph Kn+1,2n and the Complete Tripartite Graph K1,n,2n

图的厚度是指将该图分解为平面生成子图的最小数,它是衡量一个图可平面性的关键指标之一.研究一个图的厚度至关重要,它在超大规模集成电路和网络设计中有着重要应用.目前已经得到一部分图类的厚度的精确值,但完全二部图与完全三部图的厚度关系未完全得到,通过构造完全三部图K1,3p+1,6p+2的一个平面分解得到了完全三部图K1,n,2n的厚度,进而推出完全二部图Kn+1,2n与完全三部图K1,n,2n的厚度相等.

The thickness of a graph G is the minimum number of planar spanning subgraphs intOwhich can be decomposed.It is one of the key indicator for measuring the planarity of a graph. It is important tOstudy the thickness of a graph.There are many important applications in VLSI and network design.At present, the exact thickness of some types of graphs are obtained, but the relationship between the thickness of the complete bipartite graph and the complete tripartite graph has not been fully presented.In this paper,we obtain the thickness of the complete tripartite graph K 1,n,2n by constructing a planar decomposition of the complete tripartite graph K 1,3p+1,6p+2 , and get the result of the thickness of K n+1,2n and K 1,n,2n is equal.