圖G =（V,E）的強(qiáng)邊著色是將多種顏色分配給圖G的邊集,使得著每一種顏色的邊的集合是圖G的一個(gè)導(dǎo)出匹配;圖G的強(qiáng)邊色數(shù)指的是在圖G的所有強(qiáng)邊著色中需要的顏色最少的強(qiáng)邊著色的顏色數(shù),記為x’s（G）.對(duì)圖G中的一條邊e進(jìn)行剖分指的是刪除邊e,添加一個(gè)新的頂點(diǎn)x并且將x和e的兩個(gè)端點(diǎn)連接.圖G的k次剖分圖,用G（k）表示,指的是將圖G的每一條邊都恰好進(jìn)行k次剖分得到的圖.設(shè)Pm和Pu分別為包含m和n個(gè)頂點(diǎn)的路.平面（m,n）-格子圖定義為Pm和Pn的乘積圖Pm□Pn.我們用Kn表示n個(gè)頂點(diǎn)的完全圖.本文研究平面格子圖Pm□Pn的k次剖分圖的強(qiáng)邊色數(shù)以及完全圖Kn的k次剖分圖的強(qiáng)邊色數(shù).論文的主要結(jié)果如下:（1）對(duì)于平面格子圖G= Pm□Pn,當(dāng)m = 1或者n = 1時(shí),xs’（G）= e（G）若e（G）<3,x’s（G）= 3 若 e（G）≥ 3;當(dāng) m = 2,n = 2 時(shí),x’s（G）= 4;當(dāng) m = 2,n ≥ 3 或者m ≥ 3,n = 2 時(shí),x’s（G）= 6;當(dāng) m>3,n ≥ 3 時(shí),x’s（G）= 8.（2）令G（kk）是平面格子圖G = Pm□Pn的... 

【文章來(lái)源】：鄭州大學(xué)河南省 211工程院校

【文章頁(yè)數(shù)】：56 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖４平面格子圖Ｇ＝Ｐ３ＱＰ３??

圖５平面格子圖Ｇ?＝?Ｐ３ＯＰ３的一個(gè)強(qiáng)邊著色??

圖７平面格子圖Ｇ?＝巧口巧的１次剖分圖Ｇ⑴??


本文編號(hào)：2895475