K_3与偏k-树乘积的树宽

图G的树宽是使图G成为1个k-树的子图的最小整数k,也可以基于“前沿分支”的观点定义树宽.若知道1个图的树宽的下界,又能构造1种标号,使其达到下界值,则此图的树宽即能确定.笔者利用这种方法确定了K3与偏k-树乘积图的树宽,给出了它的树宽表达式及达到此树宽的标号.

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

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

树与偏k-树的乘积的树宽(英文)

本文确定了一棵树与一个ｋ－连通偏ｋ－树的乘积图的树宽．其中，偏ｋ－树是一个树宽为Ｋ的图．