图的(d,1)-全标号及游戏着色

摘要

图G的(d,1)-全标号是对顶点和边的一个整数分配,使得图G中任意两个相邻的顶点得到不同的标号,任意两条相邻的边得到不同的标号,任意顶点和与它相关联的边得到的标号差的绝对值不小于整数d.图G的(d,1)-全标号的跨度是任意两个标号差的最大值.图G的所有(d,1)-全标号的最小跨度称为(d,1)-全数.在本文第二章中给出了星图,树图和均衡完全三部图的(d,1)-全数.在第三章中给出了Sierpinski图S(n,k),Sierpinskigasket图Sn和两类Sierpinski扩充图S+(n,k)和S++(n,k)的(d,1)-全标号,进而给出了当d≥k·≥3且n≥2时λdT(S(n,k)),λdT(Sn),λdT(S+(n,k))和λdT(S++(n,k))的确切值.在(d,1)-全标号的基础上,如果顶点标号全部都在[0.△+d-1]中,则称这种(d,1)-全标号为d-好标号.在第四章中给出了当△(G)≥2d+2时,上界为2△+d-2的一种d-好标号.这个上界比以前给出的2△+d-1小,又比李国伟的条件放松.令f是一个把图H中的顶点映射到非负整数集,并且满足f(H)≤v(H)的图函数.在第五章中定义图函数f为f(K2)=2,f(P8)=3,f(C2n)=3,其余未定义的图为f(H)=0.证明了恰含有一个偶圈的单圈图的f-无圈游戏色数不超过9.

目录

摘要

Abstract

第一章 前言

1.1 选题背景和意义

1.2 图的(d,1)-全标号及游戏着色的介绍及其研究现状

1.3 预备知识

第二章 星图、树图和均衡完全三部图的(d,1)-全标号

第三章 Sierpinski-类图的(d,1)-全标号

第四章 图的一种特殊(d,1)-全标号

第五章 恰含有一个偶圈的单圈图的游戏着色

参考文献

致谢