圖的(d,1)-全標(biāo)號(hào)及游戲著色.pdf

1、圖G的(d,1)-全標(biāo)號(hào)是對(duì)頂點(diǎn)和邊的一個(gè)整數(shù)分配,使得圖G中任意兩個(gè)相鄰的頂點(diǎn)得到不同的標(biāo)號(hào),任意兩條相鄰的邊得到不同的標(biāo)號(hào),任意頂點(diǎn)和與它相關(guān)聯(lián)的邊得到的標(biāo)號(hào)差的絕對(duì)值不小于整數(shù)d.圖G的(d,1)-全標(biāo)號(hào)的跨度是任意兩個(gè)標(biāo)號(hào)差的最大值.圖G的所有(d,1)-全標(biāo)號(hào)的最小跨度稱為(d,1)-全數(shù).在本文第二章中給出了星圖,樹圖和均衡完全三部圖的(d,1)-全數(shù).在第三章中給出了Sierpinski圖S(n,k),Sierpinski

2、gasket圖Sn和兩類Sierpinski擴(kuò)充圖S+(n,k)和S++(n,k)的(d,1)-全標(biāo)號(hào),進(jìn)而給出了當(dāng)d≥k·≥3且n≥2時(shí)λdT(S(n,k)),λdT(Sn),λdT(S+(n,k))和λdT(S++(n,k))的確切值.在(d,1)-全標(biāo)號(hào)的基礎(chǔ)上,如果頂點(diǎn)標(biāo)號(hào)全部都在[0.△+d-1]中,則稱這種(d,1)-全標(biāo)號(hào)為d-好標(biāo)號(hào).在第四章中給出了當(dāng)△(G)≥2d+2時(shí),上界為2△+d-2的一種d-好標(biāo)號(hào).這個(gè)上界比以