【摘要】：圖論是離散數(shù)學(xué)的一個重要分支,圖的染色問題是圖論中重要的研究領(lǐng)域之一,其在科學(xué)技術(shù)和工程領(lǐng)域中有廣泛的應(yīng)用.在圖的染色問題中,圖的r-hued染色和距離標(biāo)號都是近幾十年來研究的熱點(diǎn),具有重要的理論研究價值與應(yīng)用前景.本論文主要研究兩類直積圖的r-hued染色和點(diǎn)積圖與無限正則三角網(wǎng)格圖的距離標(biāo)號問題.分別得到了兩類直積圖的r-hued色數(shù),點(diǎn)積圖L(2,1)-標(biāo)號數(shù)的上界和無限正則三角網(wǎng)格圖的L(3,2,1)-標(biāo)號數(shù)的新下界.論文共分五章,各章的主要工作敘述如下：第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章主要研究點(diǎn)積圖的L(2,1)-標(biāo)號問題Griggs和YeA關(guān)于圖的L(2,1)-標(biāo)號數(shù)的猜想是距離標(biāo)號問題中著名的猜想,至今仍沒有完全解決.本章通過圖的一種標(biāo)號算法和結(jié)構(gòu)分析等方法得到了點(diǎn)積圖的L(2,1)-標(biāo)號數(shù)的上界,從而也證明了對于點(diǎn)積圖,Griggs和Yeh提出的關(guān)于圖的L(2,1)-標(biāo)號數(shù)的猜想是正確的.第4章主要研究無限正則三角網(wǎng)格圖的L(3,2,1)-標(biāo)號問題.本章利用反證、結(jié)構(gòu)分析等方法得到了無限正則三角網(wǎng)格圖的L(3,2,1)-標(biāo)號數(shù)的一個新下界,改進(jìn)了已有的結(jié)果.最后,第5章對本論文進(jìn)行了簡單的總結(jié)和展望.
[Abstract]:Graph theory is an important branch of discrete mathematics. The problem of graph coloring is one of the important research fields in graph theory, and it has been widely used in science and technology and engineering. In the problem of graph coloring, the r-hued coloring and distance labeling of graphs are hot spots in recent decades, which have important theoretical research value and application prospect. In this paper, we study the r-hued coloring of two kinds of direct product graphs and the distance labeling of dot product graphs and infinite regular triangular meshes. In this paper, we obtain the r-hued chromatic number of two kinds of direct product graphs, the upper bound of the vertex product graph L (2N 1) -labeling number and the new lower bound of the L (3H 2N 1) -labeling number of infinite regular triangular meshes. The paper is divided into five chapters. The main work of each chapter is described as follows: chapter 1 briefly introduces the development of graph theory, the research background, content and preparatory knowledge of this paper. In chapter 2, we study the r-hued coloring of direct product graphs of paths and the r-hued coloring of direct product graphs of paths and cycles. Good results have been obtained on 2-hued coloring of graphs. However, there are few results about r 鈮，

本文編號：2198133