点可迁图的限制边连通性  

Restricted Edge Connectivity of Vertex Transitive Graphs

作　　者：欧见平[1] 

机构地区：[1]五邑大学数理系,江门529020

出　　处：《数学物理学报（A辑）》2005年第6期863-868,共6页Acta Mathematica Scientia

基　　金：国家自然科学基金(10271105);福建省青年人才创新基金(2003J036);福建省教育厅基金(JA03147)资助

摘　　要：3限制边割是连通图的一个边割,它将此图分离成阶不小于3的连通分支.图G的最小3限制边割所含的边数称为此图的3限制边连通度,记作λ3(G).它以图G的3阶连通点导出子图的余边界的最小基数ξ3(G)为上界.如果λ3(G)=ξ3(G),则称图G是极大3限制边连通的.已知在某种程度上,3限制边连通度较大的网络有较好的可靠性.作者在文中证明如果k正则连通点可迁图的围长至少是5,那么它是是极大3限制边连通的.A 3-restricted edge cut is an edge cut of a connected graph which separates this graph into components each having order at least 3. The minimum size of 3-restricted edge cuts of graph G is called its 3-restricted edge connectivity λ3 （G）, which is bounded above by the minimum cardinality ξ3 （G） of the coboundary of its connected vertex-induced subgraph of order 3. A graph G is called maximal 3-restricted edge connected if 23（G） =ξ3（G）. It is known that networks with greater 3-restricted edge connectivity is sense. The author proves in this paper that a connected k -regular is maximal 3-restricted edge connected if it has girth at least 5. vertex transitive graph

关 键 词：点可迁图 边连通度 限制 

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