论文部分内容阅读
图G的多级距离标号(电台标号)源于Hale的无线电频道分配问题。它足指函数f:V(G)→{0,1,2,…},使得对于图G中的任意两点u,v,满足|f(u)-f(v)|≥diam(G)+1-d(u,v),其中diam(G)表示图G的直径。max{|f(u)-f(v)|:u,v∈V(G)}称为多级距离标号f的跨度;图G的所有多级距离标号的最小跨度称为图G的多级距离数,记为rn(G)。
如果删去树T的所有悬挂点及其相关联的边后得到的是一条路或一个孤立点,则称T是一个毛毛虫。
本文主要研究了两类毛毛虫--特殊毛毛虫和关于权中心点对称的毛毛虫的多级距离标号和多级距离数。
依据内容,本文分为三个部分:
第一部分主要介绍了本文选题的背景,意义和图的多级距离标号,多级距离数的概念,国内外的研究现状以及一些预备知识。
第二部分研究的是一类特殊的毛毛虫,即除悬挂点外各点度数均相同的毛毛虫。应用反证法给出了它的多级距离数的下界;通过确定权中心点构造了一种特殊的多级距离标号并由此得出了这类特殊毛毛虫的多级距离数。
结论:1.令G=Pkt是一个特殊的毛毛虫,则(公式略)2/1(t-1)(k2-4k+8)+k-2t+1,若k为偶数。
第三部分研究的是一类具关于权中心点结构对称的毛毛虫。应用反证法和通过构造特殊的多级距离标号得出了这类关于权中心点对称的毛毛虫的多级距离数。
结论:2.令G=Pkt是一个特殊的关于权中心点对称的毛毛虫,则(公式略)。