本文關(guān)鍵詞：圖的廣義字典積與半強(qiáng)積的鄰點(diǎn)可區(qū)別和點(diǎn)可區(qū)別染色

  更多相關(guān)文章： 鄰點(diǎn)可區(qū)別邊染色 鄰點(diǎn)可區(qū)別全染色 點(diǎn)可區(qū)別邊染色 廣義字典積 半強(qiáng)積

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

【參考文獻(xiàn)】

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

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

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

，

本文編號(hào)：1281976