本科生毕业论文(或设计)
(申请学士学位)
论文题目图的顶点标号
作者姓名XXX
专业名称数学与应用数学
指导教师XX
2016年6月
学生:(签字)
学号:5060352041
论文答辩日期:2016年x月xx日
指导教师:(签字)
目录
摘 要1
Abstract1
1.绪论2
1.1背景和基本概念2
1.2已有相关结果4
2.哈密顿性和图的No-holeL(2,1)-标号5
2.1补图的哈密顿性6
2.2的图7
3.图的L(3,2,1)-标号15
3.1路和圈的L(3,2,1)-标号数15
3.2树的L(3,2,1)-标号数20
3.3一般图的L(3,2,1)-标号数21
据阶图的边数,连通分支数和直径给出了存在哈密顿路和哈密顿圈的充分条件,从而相应地得到了存在No-holelabeling的充分条件.然后我们根据这三个参数刻画的图.2.1补图的哈密顿性
我们首先引入一些记号和术语,然后研究的哈密顿性.设是一无向简单图.的顶点集和边集分别记作和.对,表示中的邻居的集合,即的邻域,表示的邻居个数,即的度.的补图是指以为顶点集的简单图使得对任意,当且仅当.对(或),(或)表示删除顶点(或边)所得到的子图.若是的子图,则是指顶点集为而边集为的子图.图和的不交并记作,是指顶点集为而边集为的图.阶的路,圈,完全图以及星分别记作,,和,特别地,就是一个孤立点.其他的一些记号和术语可参考[25].
下述定理建立了图的No-holelabeling的存在性.
定理1.1([7,14])对任一阶简单图,下面的叙述是等价的:
(1)存在一个No-holelabeling,
(2)的补图有哈密顿路,
(3).
引理1.1设是阶数最小度的简单图(1)([23])若且,则是哈密顿图,
(2)([23])若,则有哈密顿路,
(3)([24])若且对任意两个不邻接点都有,则是哈密顿图.
有,由引理1.1我们很容易得到下面相应的结果.
引理1.2设是阶数最大度的简单图.
(1)若且,则是哈密顿图,
(2)若,则有哈密顿路,
(3)若且对任意都有,则是哈密顿图.
等
等
等等
图1-1:
下面我们讨论关于补图哈密顿性的其他充分条件.
定理1.2设是阶数简单图,若边数,则是哈密顿图,若,则有哈密顿路.
证明:若,则
,(1)
由引理1.2及(1),是哈密顿图.若,对任意,有条边.从而有哈密顿圈,此时无论与否,都有哈密顿路.□