k-貝殼圖的親切標(biāo)號及若干圖的非正則和標(biāo)號.pdf

1、圖論是離散數(shù)學(xué)的骨干分支，離散數(shù)學(xué)則是計算機科學(xué)技術(shù)與網(wǎng)絡(luò)信息科學(xué)的思想基礎(chǔ)。近年來由于計算機尤其是大型計算機的發(fā)展，使得圖論在數(shù)學(xué)，物理、化學(xué)、地理、生物等基礎(chǔ)學(xué)科上面有了應(yīng)用，并且在信息科學(xué)、經(jīng)濟等眾多科學(xué)問題中有了應(yīng)用。標(biāo)號問題是圖論中比較重要的研究內(nèi)容之一。本文主要研究了親切標(biāo)號和非正則和標(biāo)號，并且取得了比較好的結(jié)果。一個有n個頂點的貝殼圖H(n,n-3)，是通過在頂點數(shù)為n的圈Cn上一個公共點u上增加n-3條邊得到的圖。令v是

2、一個在圈Cn中與u相鄰的點。Sethuramam和Selvaraju[1]猜想：當(dāng)k≥1，n≥4，1≤i≤k時，有一條公共邊(uv)的k-貝殼圖H(ni,ni-3)是親切的。 本文研究k-貝殼圖的親切標(biāo)號時，在固定了公共邊(uv)上的點的標(biāo)號(對u標(biāo)號0且v標(biāo)號為1)之后，我們采用如下方法：首先，以每個貝殼圖的頂點數(shù)對4取模的余數(shù)來分類，這樣就得到了四種不同情況的貝殼圖；然后在每個貝殼圖中再分情形進行標(biāo)號；最后，通過證明得到這種

3、標(biāo)號方法是滿足親切標(biāo)號的定義的，從而證明了k-貝殼圖的親切性，成功的解決了Sethuramam和Selvaraju猜想，證明了其正確性。Baca[2]等提出了非正則和標(biāo)號，同時提出了非正則和強度的概念。非正則和標(biāo)號分為點非正則和標(biāo)號和邊非正則和標(biāo)號。用tvs(G)和tes(G)分別表示它的點非正則和強度和邊非正則和強度。本文主要研究了廣義Petersen圖P(n,k)、梯形圖Ln、莫比烏斯梯形圖Mn、W3n、FlowerSnark及其相