任意连通图与偏k-树乘积图的树宽

Tree-width of Product of a Connected Graph and a k-connected Partial k-tree

一个图的树宽是使图成为一个k-树的子图的最小整数k,本文考虑了顶点数为m的任意连通图G与顶点数为n的k-连通的偏k-树的乘积图的树宽,首先利用对已知结构图进行树分解的方法,确定了二者乘积图树宽下界,然后结合乘积图树宽的上界,得出了在满足顶点数n≥mk的条件下二者乘积图树宽表达式。

The tree-width of a graph G is the minimum integer k subgraph of a k-tree.This paper studies the tree-width of the product of a connected graph and a k-connected partial k-tree.First,using tree-decomposition,the lower bounds of the tree-width of this graph is determined.Then using the known result of tree-width of product graph,its upper bounds is determined.So the tree-width of this graph is obtained.