图的循环标号问题

论文摘要

图论是一门应用广泛的数学分支，是组合数学的一个重要组成部分，其中图的标号问题是图论中最基本也是最重要的问题之一，它在现实生活中有很广泛的应用，关于标号问题的研究已经成为图论的新领域之一。本文主要讨论了图的循环标号问题。给定一个无向图G，G的一个L（2，1）-标号是指从其顶点集V（G）到非负整数集的一个映射f，满足：这里dG（u，v）表示u和v之间的距离，即u和v之间最短路的长度。若一个L（2，1）-标号中的所有标号都不超过整数k，则称之为k-L（2，1）-标号。图G的L（2，1）-标号数，记作λ（G），是使得图G存在L（2，1）-标号的最小正整数k。G的循环L（2，1）-标号（以后简称循环标号）是L（2，1）-标号的一种转换形式，是指映射f：V（G）→{0，1，2，…，k-1}，并满足以下条件：其中|x|k：=min{|x|，k-|x|}。若一个循环标号中的所有标号都不超过整数k-1，则称之为k-循环标号。图G的循环标号数，记作σ（G），是使得图G存在循环标号的最小正整数k。本文的主要结果有：1．路和路作Cartesian积运算后的循环标号数；2．路和圈作Cartesian积运算后的循环标号数；3．圈和圈作Cartesian积运算后的循环标号数；4．路和路作直积、强积运算后的循环标号数；5．轮图、r-路图、Mycielski图的循环标号数。

论文目录

• 摘要
• ABSTRACT
• 第一章 概述
• §1.1 基本概念
• §1.2 问题的起源与发展
• 第二章 路、圈作Cartesian积的循环标号
• §2.1 路和路作Cartesian积的循环标号
• §2.2 路和圈作Cartesian积的循环标号
• §2.3 圈与圈作Cartesian积的循环标号
• 第三章 路和路作直积、强积的循环标号
• §3.1 路和路作直积的循环标号
• §3.2 路和路作强积的循环标号
• 第四章 一些特殊图的循环标号
• §4.1 轮图的循环标号
• §4.2 r-路图的循环标号
• §4.3 Mycielski图的循环标号
• 小结
• 参考文献
• 作者申请硕士学位期间完成的工作及其参加的项目
• 致谢