【摘要】：圖論是離散數學的一個重要分支,圖的染色問題是圖論中重要的研究領域之一,其在科學技術和工程領域中有廣泛的應用.在圖的染色問題中,圖的r-hued染色和距離標號都是近幾十年來研究的熱點,具有重要的理論研究價值與應用前景.本論文主要研究兩類直積圖的r-hued染色和點積圖與無限正則三角網格圖的距離標號問題.分別得到了兩類直積圖的r-hued色數,點積圖L(2,1)-標號數的上界和無限正則三角網格圖的L(3,2,1)-標號數的新下界.論文共分五章,各章的主要工作敘述如下：第1章簡單地介紹了圖論的發(fā)展,本文的研究背景、內容以及預備知識.第2章主要研究路與路的直積圖的r-hued染色和路與圈的直積圖的r-hued染色.關于圖的2-hued染色,已經獲得了很好的研究結果.但有關r≥3的研究結果還很少,本章利用構造、反證和圖的同構等方法得到了兩類直積圖的r-hued色數.第3章主要研究點積圖的L(2,1)-標號問題Griggs和YeA關于圖的L(2,1)-標號數的猜想是距離標號問題中著名的猜想,至今仍沒有完全解決.本章通過圖的一種標號算法和結構分析等方法得到了點積圖的L(2,1)-標號數的上界,從而也證明了對于點積圖,Griggs和Yeh提出的關于圖的L(2,1)-標號數的猜想是正確的.第4章主要研究無限正則三角網格圖的L(3,2,1)-標號問題.本章利用反證、結構分析等方法得到了無限正則三角網格圖的L(3,2,1)-標號數的一個新下界,改進了已有的結果.最后,第5章對本論文進行了簡單的總結和展望.
[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