幾類圖的r-hued染色和距離標號.pdf

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

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

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