一般图的不交路划分问题  

Partition of vertex-disjoint paths in simple graphs

作　　者：张丽[1] 

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

出　　处：《云南大学学报（自然科学版）》2004年第B07期16-18,22,共4页Journal of Yunnan University(Natural Sciences Edition)

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

摘　　要：给定一个阶为n的简单图G=(V;E),其中α(G)≥4,及1个正整数k≥2,考虑在领域条件下G划分成k条点不交路的问题,并得到下面的结果:对G中任何4个独立点x1,x2,y1,y2,满足领域条件,｜NG(x1)∪NG(x2)｜+｜NG(y1)∪NG(y2)｜≥n-k-1,则要么G能划分成k条点不交的路,要么G属于一类例外图G′.Let G=(V;E) and α(G)≥4 be a simple graph oforder n and k≥2 a positive integer,consider the problem of partitioning G into k vertex-disjoint paths under the neighborhood union condition and obtain the new following results:If |N(x_1)∪N(x_2)|+|N(y_1)∪N(y_2)|≥n-k-1 for every four independent vertices,then G can be partitioned intok vertex-disjoint paths,unless G belongs to an easily recognizable classes of exception graphs.

关 键 词：简单图 领域条件 k-路划分问题 点不交路 完全图 哈密顿子图 

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