一类极大临界h连通图的结构

摘要

研究图的结构是图的连通性研究的重要内容,由轮通过一系列添边和劈开顶点的运算可以得到所有的3连通图,这是Tutte[20]给出的3连通图的简单的构造方法。对4连通图Slater[19]给出类似的构造方法,但需要4种运算。设是连通图,图的顶点称为临界点,如果不再连通。如果的每一个顶点都是临界点,则称为临界连通图。临界连通图称为极大的,如果对于中任意两个不相邻的顶点与,不再临界连通图。当图的阶一定时,边数最多的临界连通图称为最大临界连通图。一个连通图要么是临界连通图要么是极大的,否则通过添边可以使它是极大的。因而研究临暂连通图以及极大临界连通图的结构,寻找它们的构造方法就是很有意义的。对于临界2连通图,郭晓峰与朱必文[24]深入研究了它们的性质,并给出这类图的递归构造方法。对最大临界2连通图,EntrinGer[7]给出了它们的特征。Krol与Veldman[11]得到临界连通图边数的一个上界,并给出最大临界3通图的特征。对于极大临界连通图,当最小度等于时,苏健基[23]给出这一类图的一种构造Nelson[15]给出极大临界2连通图一种构造方法。文[23]中当等于2时就是极大临界2连通图,因此文[15]也给出极大临界2连通图一种新的构造方法。单就极大临力量2连通图而言,文[15]给出的构造方法比文[23]更容易操作。本文取文[23]与[15]所长,给出最小度等于的极大临界H连通图的构造方法(定理5)。定理4设是一个偶数,则是最小度等于的极大临界连通图,当且仅当或G能按下列条件先粘合中元素的H团得到H,然后H再粘合的t个拷贝得到,其中是阶大于H的一些完全图的集合：(a) 完全图的每一个顶点要么属于用于粘合中元素的H团,要么属于用于粘合的H团。(b) 如果一个H团用于粘合中元素,那么它只能用一次。如果是不同的H团,,每一个要用于粘合<；WP=4&Gt；(c) ,并且,则不能用于粘合中的元素。(d) 如果且z属于用于粘合中元素的H团,则。定理5 设H是一个偶数,则G是原子基数等于的极大临界H连通图,当且仅当,或G能按下列条件先粘合的元素的H团得到H,然后H再粘合的t个拷贝得到,其中是阶大于H的一些完全图的集合。(a) 完全图的每一个顶点要么属于用于粘合中元素的H团,要么属于用于粘合的H团。(b) 如果一个H团用于粘合中元素,那么它只能用一次。(c) 如果是不同的H团,,每一个要用于粘合,并且,则不能用于粘合中的元素。

目录

1． 内容提要

2． ABSTRACT

3． 一类极大临界h连通图的结构

4． 参考文献

5． 致谢