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

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

2、限制邊連通的：若每一個(gè)最小m限制邊割都分離出一個(gè)m階連通分支，則稱圖G是超級(jí)m限制邊連通的.用G1□G2，G1×G2分別表示圖G1與G2的笛卡爾乘積圖，直接乘積圖.在本論文中，我們得到了如下的結(jié)果： 定理2.1.7設(shè)Gi是極大邊連通ki正則圖且ki≥2，i=1，2.則G1□G2是超級(jí)限制邊連通的當(dāng)且僅當(dāng)G1□G2（）Kn□Cm。 定理2.2.9設(shè)Gi是極大邊連通ki正則圖且ki≥3，i=1，2，g（G1□G2）=3.則G

3、1□G2是超級(jí)3限制邊連通的當(dāng)且僅當(dāng)G1□G2（）Kn□G，其中G是3正則圖. 定理2.3.1設(shè)Gi是極大邊連通ki正則圖且ki≥3，g（G1）>4，i=1，2.則G1□G2是超級(jí)3限制邊連通的。 定理3.1.5設(shè)Gi是極大邊連通非偶圖，且2β（Gi）>δi，i=1，2.則G1×G2是超級(jí)邊連通的。 定理3.2.2設(shè)Gi是正則非偶圖，且ki≥3，i=1，2.若Gi是超級(jí)限制邊連通的且2β（Gi）>3ki-2.則G