| 关于路核和路剖分的新研究 |
| |
| 引用本文： | 王宝丽,李策,马丽娟.关于路核和路剖分的新研究[J].河北省科学院学报,2012,29(2):1-3. |
| |
| 作者姓名： | 王宝丽 李策 马丽娟 |
| |
| 作者单位： | 1. 北京交通大学海滨学院,河北黄骅,061100
2. 石家庄机械化步兵学院,河北石家庄,050000 |
| |
| 摘 要： | 图G的最长路的阶称为环游阶,记为τ（G）。顶点集V（G）的子集S称为图G的Pn-核,如果满足τ（GS]）≤n-1且V（G）-S的每一个顶点v都与GS]中阶为n-1路的端顶点相连。把顶点集V（G）剖分成A,B两部分,使得τ（GA]）≤a和τ（GB]）≤b,此剖分称为图G的一个（a,b）-剖分。本文证明了对于n≤3g/2-1的正整数,任意围长为g的图都有一个Pn＋1-核。并且还得到,如果τ（G）=a＋b,其中1≤a≤b,图G的围长g≥2/3（a＋1）,那么G有一个（a,b）-剖分。
|
| 关 键 词： | 路核 路半核 （a b）-剖分 路剖分猜想 |
On path kernels and partitions |
| |
| WANG Bao-li,LI Ce,MA Li-juan.On path kernels and partitions[J].Journal of The Hebei Academy of Sciences,2012,29(2):1-3. |
| |
| Authors: | WANG Bao-li LI Ce MA Li-juan |
| |
| Affiliation: | 1.Beijng Jiaotong University Haibin College,Huanghua Hebei 061100,China; 2.Shijiazhuang Mechanized Infantry Academy,Shijiazhuang 050000,China) |
| |
| Abstract: | The detour order of a graph G,denoted by τ（G）,is the order of a longest path in G.A subset S of V（G） is called a Pn-kernel of G if τ（GS]）≤ n-1 and every vertex v∈V（G）-S is adjacent to an end-vertex of a path n-1 in GS].Apartition of the vertex set of G into two sets,A and B,such that τ（GA]）≤ a and τ（GB]）≤ b is called an（a,b）-partition of G.In this paper we show that any graph with girth g has a Pn＋1-kernel for every n≤3g/2-1.Furtheremore,if τ（G）=a＋b,1≤ a≤ b,G has girth greater than g≥2/3（a＋1）,then G has an（a,b）-partition. |
| |
| Keywords: | Path kernel Path semikernel (a b)-partition Path Partition Conjecture |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
