本文關(guān)鍵詞：簡單圖的鄰和可區(qū)別邊染色

  更多相關(guān)文章： 正常邊染色 鄰和可區(qū)別的邊染色 最大平均度 平均度 平面圖 權(quán)轉(zhuǎn)移方法

【摘要】：對于圖G=(V,E),它的正常[k]-邊染色指的是G的邊集E到顏色集C=[k]={1,2,...,k}的映射φ,若對于任意兩條相互關(guān)聯(lián)的邊(?)el,e2∈E(G)有φ(e1)≠φ(e2),則稱φ是G的正常[k]-邊染色,我們用x’(G)表示使得G有正常[k]-邊染色的最小整數(shù)k.給定G的正常[k]-邊染色φ,Sφ(v)表示與v相鄰的邊的權(quán)值和,任意uv∈E(G),有Sφ(u)≠Sφ(v),稱染色φ為圖G的鄰和可區(qū)別的[k]-邊染色.我們用x’(G)表示使得G有鄰和可區(qū)別的[k]-邊染色的最小整數(shù)k.G的平均度為∑υ∈V(G)d(υ)記為ad(G).最大平均度mad(G)是G的子圖的平均度的最大值.本文主要證明了兩個(gè)定理：定理1如果G是不含孤立邊的mad(G)10/3的簡單圖,那么χΣ(G)≤k,其中k=max{△(G)+3,11}.定理2(1)設(shè)G是最大度為△,圍長為g的正常平面圖,如果g≥5,則x’Σ(G)≤k,其中k=max{△(G)+3,10}.(2)設(shè)G是最大度為△且不含4-圈的正常平面圖,則x’Σ(G)≤k,其中當(dāng)△(G)≠10時(shí),k=max{△(G)+3,13},當(dāng)△(G)=10時(shí),k=max{△(G)+ 3,14}=14.本文主要內(nèi)容具體分為三章展開：第一章,首先介紹了本文用到的基本定義和符號,其次介紹了相關(guān)概念和已得到結(jié)果,最后給出了本文要證明的兩個(gè)定理.第二章,我們利用權(quán)轉(zhuǎn)移方法證明了定理1.第三章,我們利用歐拉原理及權(quán)轉(zhuǎn)移規(guī)則構(gòu)造反例證明了定理2.
【關(guān)鍵詞】：正常邊染色 鄰和可區(qū)別的邊染色 最大平均度 平均度 平面圖 權(quán)轉(zhuǎn)移方法
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 中文摘要6-7
• 英文摘要7-9
• 第一章 緒論9-15
• §1.1 基本定義和符號9-10
• §1.2 相關(guān)概念和主要結(jié)果10-15
• 第二章 最大平均度小于10/3的鄰和可區(qū)別邊染色15-23
• §2.1 引理15-16
• §2.2 圖G的性質(zhì)16-19
• §2.3 圖H及其性質(zhì)19-20
• §2.4 權(quán)轉(zhuǎn)移規(guī)則20-23
• 第三章 平面圖的鄰和可區(qū)別邊染色23-39
• §3.1 定理2(1)的證明23-28
• §3.2 定理2(2)的證明28-39
• 參考文獻(xiàn)39-43
• 致謝43-44
• 附表44

【相似文獻(xiàn)】

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 李紅杰;簡單圖的鄰和可區(qū)別邊染色[D];山東大學(xué);2016年

  本文關(guān)鍵詞：簡單圖的鄰和可區(qū)別邊染色

  更多相關(guān)文章： 正常邊染色 鄰和可區(qū)別的邊染色 最大平均度 平均度 平面圖 權(quán)轉(zhuǎn)移方法

，

本文編號：512807