圖的循環(huán)標(biāo)號(hào)問(wèn)題.pdf

1、圖論是一門(mén)應(yīng)用廣泛的數(shù)學(xué)分支，是組合數(shù)學(xué)的一個(gè)重要組成部分，其中圖的標(biāo)號(hào)問(wèn)題是圖論中最基本也是最重要的問(wèn)題之一，它在現(xiàn)實(shí)生活中有很廣泛的應(yīng)用，關(guān)于標(biāo)號(hào)問(wèn)題的研究已經(jīng)成為圖論的新領(lǐng)域之一。 本文主要討論了圖的循環(huán)標(biāo)號(hào)問(wèn)題。給定一個(gè)無(wú)向圖G，G的一個(gè)L(2，1)-標(biāo)號(hào)是指從其頂點(diǎn)集V(G)到非負(fù)整數(shù)集的一個(gè)映射f，滿足：這里d<,G>(u，v)表示u和v之間的距離，即u和v之間最短路的長(zhǎng)度。若一個(gè)L(2，1)-標(biāo)號(hào)中的所有標(biāo)號(hào)都不超

2、過(guò)整數(shù)к，則稱(chēng)之為k-L(2，1)-標(biāo)號(hào)。圖G的L(2，1)-標(biāo)號(hào)數(shù)，記作λ(G)，是使得圖G存在L(2，1)-標(biāo)號(hào)的最小正整數(shù)к。G的循環(huán)L(2，1)-標(biāo)號(hào)(以后簡(jiǎn)稱(chēng)循環(huán)標(biāo)號(hào))是L(2，1)-標(biāo)號(hào)的一種轉(zhuǎn)換形式，是指映射f∶V(G)→{0，1，2，…，к-1)，其｜x｜<,к>∶=min{｜x｜，к-｜x｜}。若一個(gè)循環(huán)標(biāo)號(hào)中的所有標(biāo)號(hào)都不超過(guò)整數(shù)к-1，則稱(chēng)之為к-循環(huán)標(biāo)號(hào)。圖 G 的循環(huán)標(biāo)號(hào)數(shù)，記作σ(G)，是使得圖G存在循環(huán)標(biāo)號(hào)