笛卡爾乘積圖與直接乘積圖的限制邊連通性.pdf

1、本文研究正則圖的笛卡爾乘積圖與直接乘積圖的限制邊連通性，設G是任意連通圖，令β（G）=min{|S|：SСE（G）且G-S是個偶圖}.圖G的一個邊割S稱為m限制邊割，如果G-S不包含階數(shù)小于m的連通分支，圖G的最小m限制邊割的邊數(shù)λm（G）稱為它的m限制邊連通度.用ξm（G）表示只有一個端點在任意給定的m階點導出予圖中的最小邊集的邊數(shù)，已知，當m≤3且G含m限制邊割時，有λm（G）≤ξm（G）.若λm（G）=ξm（G），則稱圖G是極大m

2、限制邊連通的：若每一個最小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.則G

3、1□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.則G