笛卡尔乘积图与直接乘积图的限制边连通性

摘要

本文研究正则图的笛卡尔乘积图与直接乘积图的限制边连通性，设G是任意连通图，令β（G）=min{|S|：SСE（G）且G-S是个偶图}.图G的一个边割S称为m限制边割，如果G-S不包含阶数小于m的连通分支，图G的最小m限制边割的边数λm（G）称为它的m限制边连通度.用ξm（G）表示只有一个端点在任意给定的m阶点导出予图中的最小边集的边数，已知，当m≤3且G含m限制边割时，有λm（G）≤ξm（G）.若λm（G）=ξm（G），则称图G是极大m限制边连通的：若每一个最小m限制边割都分离出一个m阶连通分支，则称图G是超级m限制边连通的.用G1□G2，G1×G2分别表示图G1与G2的笛卡尔乘积图，直接乘积图.在本论文中，我们得到了如下的结果： 定理2.1.7设Gi是极大边连通ki正则图且ki≥2，i=1，2.则G1□G2是超级限制边连通的当且仅当G1□G2（）Kn□Cm。 定理2.2.9设Gi是极大边连通ki正则图且ki≥3，i=1，2，g（G1□G2）=3.则G1□G2是超级3限制边连通的当且仅当G1□G2（）Kn□G，其中G是3正则图. 定理2.3.1设Gi是极大边连通ki正则图且ki≥3，g（G1）>4，i=1，2.则G1□G2是超级3限制边连通的。 定理3.1.5设Gi是极大边连通非偶图，且2β（Gi）>δi，i=1，2.则G1×G2是超级边连通的。 定理3.2.2设Gi是正则非偶图，且ki≥3，i=1，2.若Gi是超级限制边连通的且2β（Gi）>3ki-2.则G1×G2是超级限制边连通的.

目录

文摘

英文文摘

声明

Chapter I Graphs and Product graphs

1.1 Edge connectivity

1.2 Cartesian and direct product graphs

Chapter 2 Edge connectivity of Cartesian product graphs

2.1 Restricted edge connectivity

2.2 3-restricted edge connectivity when g=3

2.3 3-restricted edge connectivity when g≥4

Chapter 3 Edge connectivity of direct product graphs

3.1 Super edge connectivity

3.2 Super restricted edge connectivity

References

致谢