設(shè)G為簡(jiǎn)單圖.G的全k-染色是指k種顏色1,2,…,k對(duì)圖G的全體頂點(diǎn)及邊的一個(gè)分配.設(shè)c是圖G的一個(gè)全k-染色,任意的x ∈ V（G）,稱(chēng)（?）為點(diǎn)x的擴(kuò)展和,其中N（x）={y∈ V（G）|xy ∈E（G）}.稱(chēng)圖G的全k-染色c為鄰點(diǎn)被擴(kuò)展和可區(qū)別（簡(jiǎn)記為NESD）,如果w（x）≠w（y）,其中xy∈E（G）.使得圖G存在NESD全k-染色的最小值k被稱(chēng)為圖G的鄰點(diǎn)被擴(kuò)展和可區(qū)別全色數(shù),簡(jiǎn)記為egndi∑（G）.本文利用構(gòu)造法和數(shù)學(xué)歸納法探討了一些特殊圖類(lèi)的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色,并證明了這些特殊圖類(lèi)的鄰點(diǎn)被擴(kuò)展和可區(qū)別全色數(shù)不超過(guò)2.該結(jié)論說(shuō)明Flandrin等人提出的NESDTC猜想對(duì)于這些特殊圖類(lèi)是成立的.本文的主要結(jié)構(gòu)框架是:第一章中介紹圖的鄰和可區(qū)別一般邊染色和鄰和可區(qū)別一般全染色的定義及其相關(guān)結(jié)論,進(jìn)一步提出圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色的背景及研究意義.第二章中給出圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色的相關(guān)概念,介紹關(guān)于圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色已有結(jié)論和猜想.給出整篇文章特殊圖類(lèi)的定義和相關(guān)概念.第三章中給出一些特殊圖類(lèi)的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色,并得到它們的鄰點(diǎn)被擴(kuò)展... 

【文章來(lái)源】：西北師范大學(xué)甘肅省

【文章頁(yè)數(shù)】：49 頁(yè)

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

【部分圖文】：

圖１．仙人掌圖??

定義２丄８關(guān)對(duì)ｎ，?＋１階輪ｗ？，設(shè)其頂點(diǎn)集合為ｙ（ｗｇ?＝?｛ｍ．，，爲(wèi)｝，其邊集合??為五（Ｗ’？）?＝?｛％％［？：?＝?１．，２，．…，ｗ｝Ｕ｛＇＿ｉ＋ｉ．Ｈ?＝?１，２廣，■?，ｓ?—?ｌ｝Ｕ｛ａＢ％｝．將ｗ＋?１?階輪??邊刪去之后得到的就是？１?＋?１階的扇凡，??定義２丄９＿對(duì)ｎ?＋?１階星／ｉ＼，ｎ，設(shè)其頂點(diǎn)集合為７（１＾）?＝?［％，＞ｙｉ，ｔ；２；…，％｝，其邊集合??為?＝?１，２，…；？ｉ｝．??定義２丄１０丨圳對(duì)２（ｎ＋ｌ）階的雙星氏？，設(shè)其頂點(diǎn)集合為Ｖ（‘）＝?｛如，％，％…，、物，巧，??－＾（＾４?＾?－?３？｝Ｕ?｛？〇％｝？??定義２．１．１１網(wǎng)所謂仙人掌圖（見(jiàn)圖認(rèn)就一個(gè)連通圖，其每一個(gè)塊或是圈，或是邊．記??為ｇｔ．??Ｉ??Ｉ－??圖１．仙人掌圖??定義２．１．１２＿由公共中心頂點(diǎn)如連接ｍ?xiàng)l路Ａ，ｉＶ…，的第４個(gè)頂點(diǎn)，每條路的??長(zhǎng)度都裹Ｒ?－?１（抑之２），把這ｍ?xiàng)l路分別記為只＝敏他…’％（１＜?Ｉ?ｆ?ｍ，？ｎ?２?２）５??且％與％卿相連邊，其中１?Ｓ?ｉ?Ｓ?ｍ?－?１，１?￥?ｊ＇?￥?ｎ．如此構(gòu)造的圖稱(chēng)為完全漁網(wǎng)圖（見(jiàn)??圖２），記作凡??Ｖｎ?Ｖｉ２?Ｖ１３?Ｖｉ４?Ｖｌ（ｎ－２）?Ｖ１（０－１；，?Ｖｎ??Ｏ?Ｏ——Ｏ——Ｏ?－－?ｏ￣￣ｏ￣ｏ??ｖ?ｗ，?乂－．．．．．?￣１＾￣Ｖ＇ｎ??（＾Ｋ??＼?〇——Ｓ——ｏ－——６……ｏ—ｏ＾ｏ??ｏ—ｉ—ｉ＊——６?．．．．．．?ｉｉ－￣￣ｏ——ｏ??Ｖ?ｒＹｉｉ?Ｖ?＾２?Ｖ?ｍ３?＾ｍ４?Ｖ?ｒｎ（ｎ－２）?Ｖ?ｍ（ｎ－ｌ）??圖２．完全漁網(wǎng)圖凡??４??

ｍ為偶數(shù)染顏色１?時(shí)；ｅ（＇Ｕ２ｉ—ｉ）．?＝?１．，?３?￡?２ｉ－ｌ?１；．?ｅ（？２ｉ）?＝?２，?４?仝?２？：?￥—２；其??余邊均染顏色?１?（見(jiàn)圖４），則ｗ（叫）２?９；?ｗ（ｍ２，；）?＝?４，?２?￡?２＇ｉ?ｇ?ｍ；?ｗ（他—〇?＝?６，?３?乞?２Ｚ?＿?１??Ｓ?ｒａ．?—?３；?ｗ（．ｕ？：ｉ—〇?＝?５：？顯然Ｇｗ（？ｎ?￥?３：）是鄰’點(diǎn)被擴(kuò)展和可區(qū)別的．??？？為奇數(shù)且ｆｉｉ染：顏色１?時(shí)；ｅ（：ｕ２ｉ—丄）＝２，?３?ｇ?２ｉ?－?１?－?２．；?ｅ（％ｊ）?＝?１，?４?乞?２ｉ?ｇ??ｍ?－?１；除邊如一作饑，Ｍ３Ｍ４染顏色２夕卜，其余邊均染彥異色１?（見(jiàn)圖４）．則ｗ（．％）?２?９；?ｗ（ｉｚ．２）?＝?５；??？（％）?＝?６；?ｗ（ｕ４）?＝?７］?ｍ｛ｕ，２ｉ－ｉ）?＝?４，?５?＜?２ｉ?—?１?＜?ｍ?—?２；?ｉｖ（ｕ２ｉ）?＝?６，?６?＜?２？：?＜?ｍ?—?１；??？；（、）＝?５．顯然Ｃｍ（ｍ?＞?３）是鄰點(diǎn)被擴(kuò)展和可區(qū)別的．??為偶數(shù)ｉ＆ｉ染顏色２時(shí)；�。澹ǎィ椤�；ｌ）?＝?２．；?．３?＜?２ｉ－１?＜？ｎ—?１；?ｅ（ｗＫ）?＝?１，?２?ｆ?．２４?￥?？ｎ?—２；其??余邊均染顏色?１?（．見(jiàn)圈４）．則＾（地）之?９；犯（：《３）?＝?５；?■（■＿）?＝?６，?２?竺％?ｆ?ｒａ．；ｗ（？２，；—：ｉｊ?＝?４，?５??Ｓ?２ｉ?—?１?￥?ｍ?—?１．顯ＳＣｍ（ｍ之３）是鄰點(diǎn)被擴(kuò)展和可區(qū)別的．??ｍ為奇數(shù)且ｆｆｌｉ染顏色２時(shí)；＜；（：｛％一．１）?＝?１；?３?￡?．２？：－１?＜？ｎ?—２；?ｅ（Ｍ２＇ｉ）?．２，?４?ｇ?乞?ｍ．－?１；其??余邊均染顏色．

【參考文獻(xiàn)】：
期刊論文
[1]完全漁網(wǎng)圖的鄰點(diǎn)可區(qū)別全染色[J]. 李永艷.  高師理科學(xué)刊. 2017(12)
[2]最大度為3或4的圖的鄰和可區(qū)別全染色[J]. 姚京京,徐常青.  山東大學(xué)學(xué)報(bào)(理學(xué)版). 2015(02)
[3]Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz[J]. DING LaiHao,WANG GuangHui,YAN GuiYing.  Science China（Mathematics）. 2014(09)
[4]圖Pm與Pn的Cartesian積圖的鄰點(diǎn)可區(qū)別I-全染色方法[J]. 楊曉亞.  咸陽(yáng)師范學(xué)院學(xué)報(bào). 2012(06)
[5]所有的仙人掌圖為1類(lèi)圖[J]. 許正權(quán),薛秀謙.  中國(guó)礦業(yè)大學(xué)學(xué)報(bào). 2001(01)



本文編號(hào)：3336567