幾類(lèi)圖的r-hued染色和距離標(biāo)號(hào).pdf

1、圖論是離散數(shù)學(xué)的一個(gè)重要分支，圖的染色問(wèn)題是圖論中重要的研究領(lǐng)域之一,其在科學(xué)技術(shù)和工程領(lǐng)域中有廣泛的應(yīng)用.在圖的染色問(wèn)題中，圖的r-hued染色和距離標(biāo)號(hào)都是近幾十年來(lái)研究的熱點(diǎn)，具有重要的理論研究?jī)r(jià)值與應(yīng)用前景.
　　本論文主要研究?jī)深?lèi)直積圖的r-hued染色和點(diǎn)積圖與無(wú)限正則三角網(wǎng)格圖的距離標(biāo)號(hào)問(wèn)題.分別得到了兩類(lèi)直積圖的r-hued色數(shù),點(diǎn)積圖L(2,1)-標(biāo)號(hào)數(shù)的上界和無(wú)限正則三角網(wǎng)格圖的L(3,2,1)-標(biāo)號(hào)數(shù)的新下界

2、.論文共分五章,各章的主要工作敘述如下：
　　第1章簡(jiǎn)單地介紹了圖論的發(fā)展,本文的研究背景、內(nèi)容以及預(yù)備知識(shí).
　　第2章主要研究路與路的直積圖的r-hued染色和路與圈的直積圖的r-hued染色.關(guān)于圖的2-hued染色，已經(jīng)獲得了很好的研究結(jié)果.但有關(guān)r>3的研究結(jié)果還很少,本章利用構(gòu)造、反證和圖的同構(gòu)等方法得到了兩類(lèi)直積圖的r-hued色數(shù).
　　第3章主要研究點(diǎn)積圖的L(2,1)-標(biāo)號(hào)問(wèn)題.Griggs和Yeh

3、關(guān)于圖的L(2,1)-標(biāo)號(hào)數(shù)的猜想是距離標(biāo)號(hào)問(wèn)題中著名的猜想,至今仍沒(méi)有完全解決.本章通過(guò)圖的一種標(biāo)號(hào)算法和結(jié)構(gòu)分析等方法得到了點(diǎn)積圖的L(2,1)-標(biāo)號(hào)數(shù)的上界,從而也證明了對(duì)于點(diǎn)積圖，Griggs和Yeh提出的關(guān)于圖的L(2,1)-標(biāo)號(hào)數(shù)的猜想是正確的.
　　第4章主要研究無(wú)限正則三角網(wǎng)格圖的L(3,2,1)-標(biāo)號(hào)問(wèn)題.本章利用反證、結(jié)構(gòu)分析等方法得到了無(wú)限正則三角網(wǎng)格圖的L(3,2,1)-標(biāo)號(hào)數(shù)的一個(gè)新下界,改進(jìn)了已有的結(jié)果