摘要
图G的树宽是使图G成为1个k-树的子图的最小整数k,也可以基于“前沿分支”的观点定义树宽.若知道1个图的树宽的下界,又能构造1种标号,使其达到下界值,则此图的树宽即能确定.笔者利用这种方法确定了K3与偏k-树乘积图的树宽,给出了它的树宽表达式及达到此树宽的标号.
The treewidth of graph G is the minimum integer k to make a subgraph of a k-tree by G. It can be also defined in terms of “forward component”. If the lower bound of the treewidth of a graph is known, the treewidth can be obtained by labeling construction to reach the lower lound. By this method, this paper studys the treewidth of the product of K3 and a partial k-tree and provide the expression formula of the treewidth and the corresponding labeling.
出处
《辽宁师范大学学报（自然科学版）》
CAS
北大核心
2005年第3期273-275,共3页
Journal of Liaoning Normal University:Natural Science Edition
基金
河南省教育厅基础研究项目(200410464006)
关键词
图
偏k-树
标号
树宽
graph
treewidth
partial k-tree
labeling
