本科生毕业文

更新时间:2024-01-16 作者:用户投稿原创标记本站原创 点赞:1947 浏览:5393

本科生毕业论文(或设计)

(申请学士学位)

论文题目图的顶点标号

作者姓名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),是哈密顿图.若,对任意,有条边.从而有哈密顿圈,此时无论与否,都有哈密顿路.□

相关论文范文