给定简单无向图G和非负整数m,如果对任意的不属于圈C的顶点,在G中到圈C的距离都不超过m,则称圈C为G的m-距离控制圈。设H是一个连通图的集合。若图G不含H中的任意一个元素作为导出子图,则G是H-free的。特别地,若|H|=2,则称H为一个禁用对。对于两个连通图的集合H1和H2,用H1≤H2表示对任意的H2∈H2,都有在H1∈H1,使得H1是H2的一个导出子图。本文证明了如下结论:当H≤{P5,W**}时,任意的2-连通H-free图G都含有一个1-距离控制的最长圈。
科研之友
微信
新浪微博
Facebook
分享链接
