C_(3)-和C_(4)-临界连通图的结构

Structure of C_(3)-and C_(4)-Critical Graphs

设G是连通图,如果G中每一个阶至多为m的完全子图都包含在一个最小点割内,则称G是C_(m)-临界图。Mader证明C_(3)-临界图是6连通图的,Pastor证明C_(3)-临界极小6-连通图G中由6度点导出的子图G 6的每一个分支都有一个圈。本文运用断片方法证明C_(3)-临界极小6-连通图中每一个点与至少2个6度点相邻,由此可以推出Pastor的结论。进一步,本文证明了C_(4)-临界连通图是7-连通的。

A connected graph is said to be C m-critical if every complete subgraph with order no more than m of G is contained in a smallest separating set.Mader shows that C_(3)-critical graph is 6-connected.Pastor shows that every component of G_(6),induced by the set of vertices of degree 6 of a minimally C_(3)-critical graph,has a cycle.By using some insight on properties of fragment,it is shown that every vertex of minimally C_(3)-critical graph adjacent to at least two vertices of degree 6,which implies the result of Pastor.Further,it is shown that every C_(4)-critical connected graph is 7-connected.