圖G的k-（d,1）-全標(biāo)號是對G的點和邊的以{0,1,...,k}為標(biāo)號集的一個標(biāo)號分配,使得G中相鄰的點標(biāo)號不同,相鄰的邊標(biāo)號不同,相關(guān)聯(lián)的點和邊的標(biāo)號值差至少為d.圖G的（d,1）-全標(biāo)號數(shù)λdT（G）定義為G的所有的k-（d,1）-全標(biāo)號中的最小的k值.平面圖G的k-（2,1）-點面標(biāo)號是對G的點和面的以{0,1,...,k}為標(biāo)號集的一個標(biāo)號分配,使得G中相鄰的點標(biāo)號不同,相鄰的面標(biāo)號不同,相關(guān)聯(lián)的點和面的標(biāo)號值差至少為2.平面圖G的（2,1）-點面標(biāo)號數(shù)λ2vf（G）定義為G的所有的k-（2,1）-點面標(biāo)號中的最小的k值.2002年,Havet和Yu[J]給出了（d,1）-全標(biāo)號的定義,并猜想:對任意圖G,λdT（G）≤Δ（G）+2d-1.2015年,陳東[20]給出了平面圖的（2,1）-點面標(biāo)號的定義,并猜想:對任意平面圖G,λ2vf（G）≤7.本學(xué)位論文研究了一些圖類的（2,1）-全標(biāo)號及（2,1）-點面標(biāo)號,主要分為以下三部分.第一章,我們介紹了圖論的一些基本的概念以及圖的兩類標(biāo)號問題的研究進展,并給出了本論文的主要結(jié)果.第二章,我們主要研究了外平面圖、哈林圖以及棱柱... 

【文章來源】：浙江師范大學(xué)浙江省

【文章頁數(shù)】：62 頁

【學(xué)位級別】：碩士

【部分圖文】：

()的圖示

(6)的圖示

第二章平面圖的(2,1)-點面標(biāo)號法標(biāo)號.因此,()中的點標(biāo)號只能為0和4.令()中的任意點標(biāo)號為0,那么點關(guān)聯(lián)的3個面標(biāo)號只能為2,3,4.因為()中的點標(biāo)號只能為0和4,那么標(biāo)號為3的那個面和標(biāo)號為4的那個面上與點相鄰的點將無標(biāo)號可用.這是一個矛盾.因此2(())≥5.接下來給出()的一個5-(2,1)-點面標(biāo)號即可.對于內(nèi)圈上的點1,2,...,我們依次用01(01)標(biāo)號,對于外圈上的點1,2,...,依次用10(10)標(biāo)號,對于1,2,3,...,,我們用45(45)依次循環(huán)標(biāo)號,和用3標(biāo)號.因此2(())≤5.因此當(dāng)為偶數(shù)時,2(())=5.如圖2.4,給出了(6)的一個5-(2,1)-點面標(biāo)號.圖2.4:(6)的5-(2,1)-點面標(biāo)號情況2.為奇數(shù).1.=3.假設(shè)2((3))≤5,即(3)有一個5-(2,1)-點面標(biāo)號,(3)的可用的標(biāo)號集合為{0,1,2,3,4,5}.(1)若我們令1的標(biāo)號為0,那么和1關(guān)聯(lián)的面1,3,的可用標(biāo)號為2,3,4,5.因為面1,3,兩兩相鄰,所以面1,3,的可用標(biāo)號集合可以為{2,3,4},{2,3,5},{2,4,5}或者{3,4,5}.當(dāng)1,3,中任意兩個面的標(biāo)號為2和5或者2和4時,那么1,2和3中將有一個點無法標(biāo)號,因此我們只需考慮1,3,的標(biāo)號集合為{3,4,5}的情況.若1,3,的可用標(biāo)號集合為{,,},我們需要考慮(1)=,(3)=,()=;(1)=,(3)=,()=;(1)=,(3)=,()=;(1)=,(3)=,()=;(1)=,(3)=,()=和(1)=,(3)=,()=這六種情況.因為1,3,兩兩相鄰,對于(3)來說,(1)=,(3)=,()=和(1)=,(3)=,()=是一樣的,(1)=,(3)=,()=和(1)=,(3)=,()=是一樣的,(1)=,(3)=,()=和(1)=,(3)=,()=是一樣的.因此我們只需要考慮(1)=,(3)=,()=;(1)=,(3)=,()=;(1)=,(3)=,()=這三種情況即可.20


本文編號：3406876