2-连通图中点不交路的划分问题  

On Partitioning a 2-connected Graph into Vertex-Disjoint Paths

作　　者：张丽[1] 

机构地区：[1]云南大学数学系,云南昆明650091

出　　处：《云南民族大学学报（自然科学版）》2005年第3期207-209,共3页Journal of Yunnan Minzu University:Natural Sciences Edition

基　　金：国家自然科学研究基金资助项目(编号:10271103);云南省自然科学基金资助项目(编号:2003F0015M).

摘　　要：给定一个阶为n的2-连通图G=(V;E)及一个正整数k,考虑在邻域并条件下G被分成k条点不交路的问题,得到下面的结果,对G中任何四个独立点x1,x2,y1,y2∈V,满足|NG(x1)∪NG(x2)|+|NG(y1)∪NG(y2)|n-k,则G能被分划分k条点不交的路.Let G=(V;E) be a 2-connected graph of order n and k a positive integer, we consider the problem of partitioning G into k vertexdisjoint paths under the neighborhood union condition and them obtain the new following results: If ｜N_G(x_1)∪N_G(x_2)｜+｜N_G(y_1)∪N_G(y_2)｜n-k for every four independent vertices, then G can be partitioned into k vertex-disjoint paths.

关 键 词：2-连通图 邻域并条件 点不交路 划分 

分 类 号：O157.5[理学—数学]