| 【中文题名】 | 图的循环标号问题 |
| 【英文题名】 | The Circular Labeling of Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-7-13 |
| 【中关键词】 | 频道设置问题,L（2,1）-标号,循环标号,Cartesin积,直积 |
| 【英关键词】 | L（2,1） - labeling,Channel assignment problem,Circular labeling,Cartesian Product,Direct Product,Strong Product, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
图论是一门应用广泛的数学分支，是组合数学的一个重要组成部分，其中图的标号问题是图论中最基本也是最重要的问题之一，它在现实生活中有很广泛的应用，关于标号问题的研究已经成为图论的新领域之一。
本文主要讨论了图的循环标号问题。给定一个无向图G，G的一个L(2，1)-标号是指从其顶点集V(G)到非负整数集的一个映射f，满足：这里d_G(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．路和圈作... |
| 【论文题纲】 |
|
摘要 |
6-8 |
|
ABSTRACT |
8-11 |
|
第一章 概述 |
11-18 |
|
§1.1 基本概念 |
11-13 |
|
§1.2 问题的起源与发展 |
13-18 |
|
第二章 路、圈作Cartesian积的循环标号 |
18-31 |
|
§2.1 路和路作Cartesian积的循环标号 |
18-19 |
|
§2.2 路和圈作Cartesian积的循环标号 |
19-24 |
|
§2.3 圈与圈作Cartesian积的循环标号 |
24-31 |
|
第三章 路和路作直积、强积的循环标号 |
31-36 |
|
§3.1 路和路作直积的循环标号 |
31-33 |
|
§3.2 路和路作强积的循环标号 |
33-36 |
|
第四章 一些特殊图的循环标号 |
36-40 |
|
§4.1 轮图的循环标号 |
36-37 |
|
§4.2 r-路图的循环标号 |
37-38 |
|
§4.3 Mycielski图的循环标号 |
38-40 |
|
小结 |
40-41 |
|
参考文献 |
41-44 |
|
作者申请硕士学位期间完成的工作及其参加的项目 |
44-45 |
|
致谢 |
45 |
|
| 【DOI】 | LunWen.ID:2.2008.11793 |
