本文關鍵詞：圖的廣義字典積與半強積的鄰點可區(qū)別和點可區(qū)別染色

  更多相關文章： 鄰點可區(qū)別邊染色 鄰點可區(qū)別全染色 點可區(qū)別邊染色 廣義字典積 半強積

【摘要】：本文研究了圖的廣義字典積的鄰點可區(qū)別邊染色與鄰點可區(qū)別全染色,以及圖的半強積的點可區(qū)別邊染色與鄰點可區(qū)別全染色,并利用圖分解技術與構造染色的方法給出了相應染色數(shù)的可達上界.在此基礎上,確定了一些特殊圖的廣義字典積與半強積的相應染色數(shù)的精確值.主要結果包括四個部分：第 ,得到了圖G與圖序列hp=(Hi)i∈{0,1...,n-1}的廣義字典積G[hn]的鄰點可區(qū)別邊色數(shù)的兩個上界：(1)若G存在χ'as(G)-鄰點可區(qū)別邊染色,使得該染色中某一色類的邊將G的所有最大度點全部飽和,則χ'as(G[hn])≤mχ'as(G)+χ'(H0)+1,其中χ'(H0)=max{χ'(Hi)|ti∈V△(G)},且V△(G)表示G的最大度點構成的集合.(2)χ'as(G[hn])≤mχ'as(G)+χ'as(H0),其中χ'as(H0)=max{χ'as(Hi)|ti∈V△(G)}.驗證了以上兩個上界是可達的.并對滿足χ'as(G)=△(G)的圖G,給出了當H0分別為完全圖和樹時廣義字典積G[hn]的鄰點可區(qū)別邊色數(shù)的精確值.對滿足χ'as(G)=△(G)和χ'as(H)=△(H)的圖G與H的兩個字典積G[H]與H[G],確定了它們的鄰點可區(qū)別邊色數(shù).另外,對最大度相等且鄰點可區(qū)別邊色數(shù)為其最大度的p個連通圖的字典積Gp[Gp-1[…G2[G1]…]],得到了它的鄰點可區(qū)別邊色數(shù),并證明該色數(shù)與G1,G2,…,G。的順序無關.第二,得到了n≥6階輪或扇或星與m≥2階連通圖序列hn=(Hi)ie{0,1,...,n-1}的廣義字典積G[hn]的鄰點可區(qū)別全色數(shù)的一個可達上界：χ'at(G[hi])≤m(m-1)+min{χr(H0)+1,χat,(H0)},其中H0與G的最大度點t0對應.并利用該結果給出了當H0分別為樹、圈、路、完全圖、正則二部圖時G[hn]的鄰點可區(qū)別全色數(shù)的精確值.第三,得到了階至少為3的兩個簡單聯(lián)通圖G與H的半強積G·H的點可區(qū)別邊色數(shù)的一個可達上界：χ'vd(G·H)≤△(H)χ'vd(G)+χ'vd(H).在此基礎上,對于滿足χ'vd(G)=△(G)的圖G,得到了G與滿足χ'vd(H)=△(H)的圖H的半強積,以及G與完全圖的半強積的點可區(qū)別邊色數(shù)的精確值.另外,對最大度相等且點可區(qū)別邊色數(shù)為其最大度的p個連通圖的半強積Gp·(Gp-1·(…·(G2·G1)…)),確定了它的點可區(qū)別邊色數(shù),并證明該色數(shù)與G,,G2,…,Gp的順序無關.第四,得到了階至少為2的兩個簡單連通圖G與H的半強積G·H的鄰點可區(qū)別全色數(shù)的一個可達上界：χol,(G·H)≤△(H)χ'(G)+χal(H).并利用該上界給出了第一類圖與非平凡樹、圈的半強積,兩個正則二部圖的半強積,以及兩個非平凡樹的半強積的鄰點可區(qū)別全色數(shù)的精確值.另外,得到了p個非平凡樹的半強積Tp-1,·(Tp-2·(…·(T1·T0)…))的鄰點可區(qū)別全色數(shù).
【學位授予單位】：西北民族大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前2條

1 李明哲,劉林忠,張忠輔;圖P_2×C_n 的均勻鄰強邊色數(shù)(英文)[J];經(jīng)濟數(shù)學;2002年03期

2 田雙亮;陳萍;;若干多重聯(lián)圖的邊染色[J];南開大學學報(自然科學版);2007年03期

，

本文編號：1281976