| 【中文题名】 | 平方图的点荫度 |
| 【英文题名】 | Vertex Arboricity of Square Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-7-19 |
| 【中关键词】 | 点荫度,点线性荫度,平方图,树,外平面图,K_4 |
| 【英关键词】 | vertex arboricity,vertex linear arboricity,square graph,tree,outerplanar graph,K_4 minor free graph,planar graph,product graph, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
本文中考虑的图都是简单图。分别用V(G)，E(G)，|G|，Δ(G)，δ(G)表示图G的点集合，边集合，点的个数，最大度和最小度。对x∈V(G)，用N_G(x)表示在G中与点x相邻的所有点的集合，用d_G(x)表示点x的度。度为k的点称为k-度点。
设G是一个图，G的一个k-着色f是从V(G)到1，2，…，k的一个映射。对于图G的给定的k-着色，V_i表示G中所有染i色的顶点集(1≤i≤k)，表示G中由V_i导出的子图，若对于任意的i(1≤i≤k)，都有是森林，则称f是一个k-树着色。使G有k-树着色的最小数k称为图G的点荫度，记为va(G)。若对于任意的i(1≤i≤k)，都有的每个连通分支都是路，则称f是一个k-路着色。使得图G有k-路着色的最小正整数k称为图G的点线性荫度，记为vla(G)。显然va(G)≤vla(G)≤x(G)。
任意两点u，v∈V(G)，它们之间的距离为连接这两个点的最短路的长度，用dist_G(u，v)表示。图G的平方图G~2是以V(G)作为它的点集，两个点u，v在G~2中相邻当且仅当1≤dist_G(u，v)≤2。
对... |
| 【论文题纲】 |
|
中文摘要 |
6-8 |
|
英文摘要 |
8-10 |
|
第一节 综述 |
10-14 |
|
第二节 树的平方图的点荫度和点线性荫度 |
14-17 |
|
第三节 外平面图的平方图的点荫度 |
17-20 |
|
第四节 K_4 minor free图的平方图的点荫度 |
20-23 |
|
第五节 平面图的平方图的点荫度 |
23-27 |
|
第六节 乘积图的点荫度和点线性荫度 |
27-29 |
|
参考文献 |
29-33 |
|
致谢 |
33-34 |
|
学位论文评阅及答辩情况表 |
34 |
|
| 【DOI】 | LunWen.ID:2.2008.11825 |
