关于毛毛虫的优美问题.pdfVIP

第22卷 第6期 内蒙古民族大学学报(自然科学版) Vo1．22 No．6 2007年12月 JournalofInnerMongoliaUniversityforNationalities Dec．2007 关于毛毛虫的优美问题 冀爱萍，张天宇 (内蒙古民族大学数学与计算机科学学院，内蒙古通辽 028043) [摘 要]关于毛毛虫的优美问题有不同的解决方法，其中毛毛虫优美标号的逐步构造方法简便易行，然而，在 文献中由于其证明有些漏洞而往往引起读者对这种方法的可靠性的怀疑，本文将补充这个漏洞． [关键词]优美图；优美标号 [中图分类~]O157．5 [文献标识码]A [文章编~-]1671—0185(2007}06—0611—03 On the Beautiful Graph of Caterpillar 儿Ai—ping，ZHANG Tian—yu (College of Mathematics and Computer Science，Inner Mongolia University for Nationalities，Tongllao 028043，China) Abstract：There are many different methods on the beauty of caterpillar graph problem．Among them，the method of gradually constructing the beautiful mark is much easier．But as in refer— ences，there are some leaks of proving that often makes the readers suspect the reliability of this method．So in regard to the leaks this article will give the supplement of it． Key words：Beautiful graph；Beautiful mark number 1 引言 随着计算机的发展，图的标号在网络和通讯等领域中的应用越来越广泛，而优美图也是如此．因此寻 找某些图的优美标号，便成了组合理论研究的活跃课题，但鉴于缺乏系统和有力的理论工具，迄今为止国 内外学者还只限于对某些特殊图类，探索其优美性，已有典型结果见文献[1]． 定义1 对于一个简单图G=(V，E)，若对每一个 ∈V，存在一个非负整数0( )(称为顶点 的 标号)使满足： (1)任意的“， ∈V，若“≠ ，则 (“)≠ ( )； (2)max{ ( )I ∈V}= I E I； (3)V el，e2∈E，如果el≠e2，则0 (e1)≠0 (e2)．这里0 (e)= 1 0(“)一0( )I，其中e=zc ． 称G为优美图，0称为G的优美标号． 2 优美标号的个数 定理1 全体m条边的连通图的所有优美标号的个数是m!个． 证 我们考虑顶点标号后，两数之差分别为1，2，…，m的所有情形，列于下表： 收藕日期：2007一O8—25 作者简介：冀爱萍(1972一)，女，内蒙古通辽市人，讲师，主要从事高等数学研究． 612 内 蒙 古 民 族 大 学 学 报 2007年 7挖 优 一1 优 一2 优 优 优 ，) (仇，仇一2)，(仇一1，仇一3)，…，(3，1)，(2，0) 优 优 (仇，仇一1)，(仇一1，仇一2)，…，(2，1)，(1，0) 上表中每对数代表图中的一条边，每行取一对