关于Pseudo-split图的一点推广  

A Generalization of Peudo-split Graph

作　　者：薛清波[1] 孙大宁[1] 唐旭辉[1] 

机构地区：[1]北方工业大学基础学院,北京石景山100041

出　　处：《北方工业大学学报》2000年第1期41-44,共4页Journal of North China University of Technology

基　　金：北方工业大学科研基金资助项目

摘　　要：继 Ham m er和 Fo··ldes提出 split图的概念 ,并证明 split图即是 ( C4,C5 ,2 K2 ) -free图之后 ,1994年 ,Frederic Maffray和 Myriam Preissmann给出了 ( C4,2 K2 ) -free图 ( pseu-do-split graphs)的结构特点 .我们将 2 K2 -free这个条件减弱为 ( F1 ,F2 ) -free后 ,得出结论 :一个连通图是 ( C4,F1 ,F2 ) -free的 ,其最大的一个团中点的个数至少为 3 ,且不是一个三角剖分图 ( triangulated graph)的充分必要条件为 :其点集可被划分为 A,B,C3个部分 ,其中 A导出一个团 ,B导出一个独立集 ,C导出一个 Cn( n>4) ,而 A与 C之间有所有可能的线 ,B与Hammer and Fo··ldes proposed the concept of split graph and proved that a split graph was a ( C 4, C 5,2 K 2)-free graph. In 1994,Frederic Maffray and Myriam Preissmann found out the structural character of ( C 4,2 K 2)-free graphs (pseudo-split graphs). After reducing the condition 2 K 2-free to ( F 1, F 2)-free, the paper comes to the following conclusion: A connected graph is ( C 4, F 1, F 2)-free and is not a triangulated graph and its clique number is at least 3, if and only if: its vertex set can be partitioned into three sections A,B,C , where A induces a clique,B induces a stable set, C induces a C n(n >4), and there are all possible edges between A and B , and no edge between B and C .

关 键 词：完美园 连通图 Pseudo-split图 三角剖分图 

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