| 树的线图的图扩充问题 |
| |
| 引用本文： | 侯亚林,张振坤,李学志.树的线图的图扩充问题[J].数学的实践与认识,2009,39(16). |
| |
| 作者姓名： | 侯亚林 张振坤 李学志 |
| |
| 作者单位： | 1. 黄淮学院数学科学系,河南,驻马店,463000
2. 信阳师范学院数学与信息科学院,河南,信阳,464000 |
| |
| 基金项目： | 河南科学发展计划基础与前沿技术研究项目，河南省高科技创薪人才支持计划资助 |
| |
| 摘 要： | 图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G).对一般图而言,它们都是NP-困难问题.一些特殊图类的填充数、树宽、侧廓问题和路宽具体值已被求出.主要研究树T的线图L(T)的弦图扩充问题;其次涉及到了两类特殊树—毛虫树和直径为4的树的线图的区间图扩充问题.
|
| 关 键 词： | 填充数 树宽 侧廓 树 线图 |
Graph Extention Problem for Line-graphs of Trees |
| |
| HOU Ya-lin,ZHANG Zhen-kun,LI Xue-zhi.Graph Extention Problem for Line-graphs of Trees[J].Mathematics in Practice and Theory,2009,39(16). |
| |
| Authors: | HOU Ya-lin ZHANG Zhen-kun LI Xue-zhi |
| |
| Abstract: | Chordal graph extention includes two problems: the minimum fill-in problem and the treewidth problem,denoted as f(G) and TW(G) respectively;interval graph extention problem contains two problems: the profile problem and the pathwidth problem too,denoted as P(G) and PW(G) respectively.The four problems are known to be NP-hard for general graphs.Some classes of special graphs have been investigated in the literatures.In this paper we investigate maily the chordal graph extention problem of the line-graph L(T) for any tree T;And the interval graph extention problem for line-graph L(T) of any caterpillar and any tree with diameter 4,is studied secondly. |
| |
| Keywords: | fill-in number treewidth profile pathwidth tree line-graph |
| 本文献已被 万方数据 等数据库收录！ |
|
