任意连通图与偏k-树乘积图的树宽 (2008年)

【文件属性】：

文件名称：任意连通图与偏k-树乘积图的树宽 (2008年)

文件大小：122KB

文件格式：PDF

更新时间：2024-07-08 08:59:20

自然科学 论文

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