几类图的r-hued染色和距离标号
发布时间：2018-08-22 19:48
【摘要】：图论是离散数学的一个重要分支,图的染色问题是图论中重要的研究领域之一,其在科学技术和工程领域中有广泛的应用.在图的染色问题中,图的r-hued染色和距离标号都是近几十年来研究的热点,具有重要的理论研究价值与应用前景.本论文主要研究两类直积图的r-hued染色和点积图与无限正则三角网格图的距离标号问题.分别得到了两类直积图的r-hued色数,点积图L(2,1)-标号数的上界和无限正则三角网格图的L(3,2,1)-标号数的新下界.论文共分五章,各章的主要工作叙述如下：第1章简单地介绍了图论的发展,本文的研究背景、内容以及预备知识.第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
[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
本文链接：https://www.wllwen.com/kejilunwen/yysx/2198133.html
