图的若干标号问题

发布时间：2021-09-24 02:04

　　图G的k-（d,1）-全标号是对G的点和边的以{0,1,...,k}为标号集的一个标号分配,使得G中相邻的点标号不同,相邻的边标号不同,相关联的点和边的标号值差至少为d.图G的（d,1）-全标号数λdT（G）定义为G的所有的k-（d,1）-全标号中的最小的k值.平面图G的k-（2,1）-点面标号是对G的点和面的以{0,1,...,k}为标号集的一个标号分配,使得G中相邻的点标号不同,相邻的面标号不同,相关联的点和面的标号值差至少为2.平面图G的（2,1）-点面标号数λ2vf（G）定义为G的所有的k-（2,1）-点面标号中的最小的k值.2002年,Havet和Yu[J]给出了（d,1）-全标号的定义,并猜想:对任意图G,λdT（G）≤Δ（G）+2d-1.2015年,陈东[20]给出了平面图的（2,1）-点面标号的定义,并猜想:对任意平面图G,λ2vf（G）≤7.本学位论文研究了一些图类的（2,1）-全标号及（2,1）-点面标号,主要分为以下三部分.第一章,我们介绍了图论的一些基本的概念以及图的两类标号问题的研究进展,并给出了本论文的主要结果.第二章,我们主要研究了外平面图、哈林图以及棱柱... 

【文章来源】：浙江师范大学浙江省

【文章页数】：62 页

【学位级别】：硕士

【部分图文】：

()的图示

(6)的图示

第二章平面图的(2,1)-点面标号法标号.因此,()中的点标号只能为0和4.令()中的任意点标号为0,那么点关联的3个面标号只能为2,3,4.因为()中的点标号只能为0和4,那么标号为3的那个面和标号为4的那个面上与点相邻的点将无标号可用.这是一个矛盾.因此2(())≥5.接下来给出()的一个5-(2,1)-点面标号即可.对于内圈上的点1,2,...,我们依次用01(01)标号,对于外圈上的点1,2,...,依次用10(10)标号,对于1,2,3,...,,我们用45(45)依次循环标号,和用3标号.因此2(())≤5.因此当为偶数时,2(())=5.如图2.4,给出了(6)的一个5-(2,1)-点面标号.图2.4:(6)的5-(2,1)-点面标号情况2.为奇数.1.=3.假设2((3))≤5,即(3)有一个5-(2,1)-点面标号,(3)的可用的标号集合为{0,1,2,3,4,5}.(1)若我们令1的标号为0,那么和1关联的面1,3,的可用标号为2,3,4,5.因为面1,3,两两相邻,所以面1,3,的可用标号集合可以为{2,3,4},{2,3,5},{2,4,5}或者{3,4,5}.当1,3,中任意两个面的标号为2和5或者2和4时,那么1,2和3中将有一个点无法标号,因此我们只需考虑1,3,的标号集合为{3,4,5}的情况.若1,3,的可用标号集合为{,,},我们需要考虑(1)=,(3)=,()=;(1)=,(3)=,()=;(1)=,(3)=,()=;(1)=,(3)=,()=;(1)=,(3)=,()=和(1)=,(3)=,()=这六种情况.因为1,3,两两相邻,对于(3)来说,(1)=,(3)=,()=和(1)=,(3)=,()=是一样的,(1)=,(3)=,()=和(1)=,(3)=,()=是一样的,(1)=,(3)=,()=和(1)=,(3)=,()=是一样的.因此我们只需要考虑(1)=,(3)=,()=;(1)=,(3)=,()=;(1)=,(3)=,()=这三种情况即可.20


本文编号：3406876