点可迁图的顶点划分  

Partition of Vertex Transitive Graphs

作　　者：欧见平[1] 张福基[1] 

机构地区：[1]厦门大学数学系,福建厦门361005

出　　处：《厦门大学学报（自然科学版）》2003年第1期9-11,共3页Journal of Xiamen University：Natural Science

基　　金：国家自然科学基金资助项目(19971071)

摘　　要：设G是k正则连通点可迁图.图G的一个边割S称为限制性边割,如果G-S不含孤立点.最小限制性边割所含的边数λ′称为限制性边连通度.已经证明λ′≤2k-2.等号成立时,称图G是极大限制性边连通的.本文证明了:如果G不是极大限制性边连通的,那么G的顶点集存在一个划分π=(C1,…,Cm),使得由Ch导出的子图同构于一个连通k-1正则点可迁图H,h=1,2,…,m,而且k≤｜H｜≤2k-3.Let G be a connected kregular vertex transitive graph. An edge cut S of G is called a restricted edge cut if G-S contains no isolated vertex. The cardinality λ′ of minimum restricted edge cut is called restricted edge connectivity. It is known that λ′≤2k-2. A graph G is maximal restricted edge connected if λ′=2k-2. We prove in this paper that if G is not maximal restricted edge connected, then there is a vertex partition π=(C1,...,Cm) in G such that G is isomorphic to a connected (k-1)regular vertex transitive graph H with order between k and 2k-3 for all h=1,2,...,m.

关 键 词：点可迁图 顶点划分 限制性边割 限制性断片 正则图 连通图 边连通度 

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