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