（运筹学与控制论专业论文）边优美图研究的若干结果.pdf

边优美图研究的若干结果 彭锦 摘要：本文研究图的边优美性问题首先探讨了边优美图的必要条 孛，同时绘蹬了垂已知遗优美图褥到耨的选捷美翻妁两个充分袈终；其 次，考察了几稀特殊匿粪成为透傀荑鬻鳃特征；再赣，梅造了一类奇阶偶 正则的边优美图然后，主要证明了几类奇阶树都怒边优美树最后，提出 了边优美图课题中边优美树猜想等值得进一步研究的若干问题或猜想 关键溺；速撬美蚕；鸯夔馁委粼逮爨美虱遗俊美挺 s o m er e s u l t so n e d g e - - g r a c e f u lg r a p h s p e n gj i n a b s t r a c t ：t h i st h e s i s d e a l sw i t ht h e e d g e g r a c e f u l n e s s o f g r a p h s f i r s t l y ，w ei n v e s t i g a t et h en e c e s s a r yc o n d i t i o n so fe d g e - - g r a c e f u l g r a p h s ，a n dp r o v i d et w os u f f i c i e n tc o n d i t i o n sf o ro b t a i n i n ge d g e - - g r a c e f u lg r a p h s ；s e c o n d l y ，w ei n s p e c tt h es i m p l ec h a r a c t e r i s t i c so f8 0 m e s p e - c i a lc l a s s e so fe d g e - - g r a c e f u lg r a p h s ；t h i r d l y ，w ec o n s t r u e ta c l a s s 。f e v e n r e g u l a re d g e g r a c e f u lg r a p h sw i t ho d do r d e r ；t h e nw em a i n l y p r o v et h a tan u m b e ro ft r e e sw i t ho d do r d e ra r ee d g e - - g r a c e f u l f i n a l l y ， w ep r o p o s es o m e o p e np r o b l e m so rc o n j e c t u r e sf o rf u r t h e rr e s e a r c h 。 k e y w o r d s ：e d g e - - g r a c e f u lg r a p h s ；e v e n r e g u l a re d g e g r a c e f u lg r a p h s w i t ho d do r d e r ；e d g e g r a c e f u lt r e e s 1 引言 图的标号问题源于6 0 年代中期g r i n g e l 和a + r o s a 提出的优美树 猜斛m ，现在已经形成组合理论中一个重要而活跃的研究分支领域。著 名的r i n g e l - - k o t z i g 猜想：所有的树都是优美的迄今为止，此猜想尚未 获得完全证明围绕这个诱人的猜想，国内外学者在图的标号课题方面 开展了大量的工作。_ 9 3 图的标号问题之所以引人注目，一方面是由于优 美树猜想的光彩耀眼，另一方面，它在诸如编码理论、x 一射线晶体学、雷 达、天文学、循环设计、通讯网络等理论或实际中有广泛的应用c 1 0 - - 1 4 3 图的标号问题有各种各祥的提法，归纳起来可以分为两大类；一类是 顶点标号问题，另一类则是边标号问题 点标号问题都是在一定条件要求下对图的顶点标号( 或赋值) ，使得 按某种方法导出的边标号满足指定的性质图的点标号又可分为如下几 种：点优美标号。”一个简单图g 一，e ) 称为( 点) 优美的，如果 存在从顶点集y 到集合s 一 0 ，1 ，q ( 口一l e | ) 的单射z ，使得导 出的边标号l7 ( “”) 一lz ( “) - - i ( ”) i 对每条边“。都有不同的标号此 时z 称为g 的( 点) 优美标号点优美标号的限制或推广。6 _ 2 ”例如： n 一标号。”，一优美标号“。等对于正整数k ，简单图g = ( y ，e ) 称 为 优美的，若存在单射，：y 一 o ，1 ，2 ，l e i + 一1 ) ，使得由 之导出的映射，。：e 一 k ，k + 1 ，fei + k 一1 ) ，f ( 。口) 一 i ，( “) - - f ( ”) i 是双射o “”3 协调标号1 9 8 0 年由g r a h n m 和 s l o a n e 提出一个具有q 条边的简单图g 称为协调的，若存在由g 的顶 点集矿到模q 的整数量的一个单射h ，使得导出映射h ”：e z 0 ，h + ( “口) ； ( “) + ( 口) ( m o d 口) 为双射“5 2 “”。”协调标号的限制或推 广例如，强协调标号o “”3 ，序列标号“。”2 “”1 一个具有q 条边的简单 图g 称为序列图，如果存在从g 的顶点集y 到模q 的整数群乙的单射， 使得导出的边标号g ( “”) ；g ( “) + g ( ”) 是一个等差数列 ，k + 1 ， + 2 ，e + g 一1 ) ，此时g 称为g 的序列标号算术标号c 2 7 , 2 8 ) 等 1 。 对于给定的两个正整数k ，d ，一个( 户，g ) 图g 称为( ，j ) 一算术 图，如果存在从g 的顶点集v 到非负整数集z o 的单射，：y z 0 ，使得 导出的边标号f 。( “v ) 一，( + ，o ) 组成算术序列 k ，k + d ， + 2 d ， + ( 口一1 ) d ) 序列图是协调图，并且是( ，1 ) 一算术图 图的上述点标号中，最具有代表性和影响性、最富有重要性和趣味性的当 为优美标号“优美”一词是g o l o m b 首先使用而后被广泛采用。”图的带 宽与图的点标号之间有一定的联系。”图的优美标号和协调标号研究至 今主要局限于一些特殊图类，即使如此也存在大量悬而未决的问题。1 图的另一类标号问题一一边标号问题就是在一定条件要求下对图的 边进行标号，使得按某种方法产生的顶点标号满足指定的性质边标号 目前主要有如下两种提法：边幻方标号0 2 “”设g 一( y ，e ) 为简单 图，l y i p ，i e i q 如果存在双射厂：e 一( 1 ，2 ，q 使得映射，+ ： y 一( 0 ，1 ，户一1 成为常值映射，此处导出映射，+ ( ”) 一善f ( u v ) ( r o o d 户) ，则称g 为边幻方图，而，称为g 的边幻方标号边优美 标号。”在1 9 9 6 年6 月召开的第八届图论、组合学、算法和应用国际会 议上，s i n 一胁nl e e 等人再次提出了图的边优美标号的概念( 参见本文 下节) ，并在该会上报告了两个结果：( 1 ) 广义p e t e r s e n 图p ( n ，k ) 是 边优美的当且仅当n o ( r o o d2 ) 且 詈( 2 ) 棱柱c 。k 。是边优美的 当且仅当n ；- - 0 ( r o o d2 ) ，于是很自然地提出问题：其它图类的边优美性 如何? 对边优美图的研究目前处于起点阶段，国内隧末发表此课题的公开 论文，国外研究的成果也不多“m 本文研究图的边优美问题，首先探讨了边优美图的必要条件，同时给 出了由已知的边优美图得到新的边优美图的两个充分条件；其次，考察了 几种特殊图类成为边优美图的简明特征；再者，构造了一类奇阶偶正则的 边优美图；然后，主要证明了几类奇阶树都是边优美树；最后，提出了边 优美图课题中值得进一步研究的若干问题与猜想 2 基本概念和预备知识 本文讨论的边优美图均指无向的有限简单图，未加说明的一般术语 。 的局部点迁树记为丁7 若p 阶树丁带有边标号厂：e 一 1 ，2 ， 口) ，当t 。的根点“的出边标号之和是p 的倍数时，则称局部点迁树 7 ”。为t - 的模p 局部点迁树记为了”。厶( 图示参见后面3 4 例1 ) 3 主要结果 3 1 边优美图的必要条件及充分条件 寻求一般图是边优美图的充要条件是很困难的事实上，即使是对 一些特殊图类给出边优美的特征也并非轻而易举本节给出了图成为边 优美图的必要条件，由此，可简便判别很多图不是边优美的；另一方面， 给出了一类添边图或删边图成为边优美的充分条件，利用它借助于已有 的边优美图可得到新的边优美图 定理1 设g 一( y ，e ) 为( 户，g ) 图若g 为边优美图，则g 的点 数p 与边数q 必满足q ( 口- f - 1 ) 一p 色掣 ( i ) 证明设y 一( 口o ，口l ，口，一1 ) ，e = e 1 ，e 2 ，岛) ，因为g 是 边优美图，所以存在边优美标号_ 厂：e 一( 1 ，2 ，q 记厂( q ) 一n ， j = 1 ，2 ，q 此处a i ，n2 ，是1 ，2 ，g 的某一个q 元排列 于是由双射，诱导出的顶点标号，+ ：y 一 0 ，1 ，声一1 ) 为”v i ) = 墨。，( “口，) p - - b ，i = 0 ，l ，户一1 其中6 。，6 1 ，6 p 一1 是o ，1 ， ，户一1 的某个p 元排列由于g 中每条边与其两个端点关联，利用求 和公式得： ，一lp 1口 ，+ ( 口，) 一f ( u v 。) 一2 a ，；2 ( 1 + 2 + 口) 一q ( q + 1 ) ， r 2 0 “口ej = l 6 l o + 1 + 2 + 户一1 一之掣 l = o o 由同余的可加性得，g ( q + 1 ) 一p 生掣证毕 定理2 设g 为( p ，q ) 图，且户l q 或p l ( q + 1 ) 若g 为边优美 图，则g 必为奇阶图 r 证明由定理1 及条件p i 口或p i q + 1 知正掣皇。从而也 为 整数，故p 必为奇数证毕 注意到对于树、单圈图等图类，条件“p i q 或p l ( q + 1 ) ”成立，故 得如下一系列推论： 推论l 若树7 是边优美树，则i y ( 丁) 为奇数 推论2 若单圈图g 是边优美图，则i v ( g ) l 为奇数 推论3 若环而格c 。c 。为边优美图，则m ，”皆为奇数 证明由于c 。c 。有z 个顶点，2 r a n 条边，所以由定理2 知m n 为 奇数，从而m ，n 皆为奇数证毕 推论4 偶正则的边优美图必是奇阶的 证明设2 r 度正则图g 边优美，则户2 r = 2 q ，故p l q 于是p 必为 奇数即不存在偶阶偶正则的边优美图证毕 当p 为素数时，由定理1 中( i ) 式知q ( q + 1 ) - po ，于是户i q 或 p i 口+ 1 故得 定理3 素数阶( 户，q ) 图g 若是边优美图，则其点数与边数必有关 系p i q 或p i ( q + 1 ) 定理4 设g 一( v ，e ) 为( 户，口) 图，若g 为边优美图，则： ( 1 ) 当p 为奇数时，p l q ( g + 1 ) _ ( 1 ) 当户为偶数时，p - - - ；0 ( r o o d4 ) 证明( 1 ) 由定理1 中( i ) 式即得 ( 2 ) 。p 为正偶数 。卢一4 k 或4 + 2 ( z + ) 因g 为边优美图， 故由定理1 中( i ) 式有q ( q + 1 ) 一p 色掣 假若p = 4 k + 2 ，则q ( 口十1 ) 竺( 2 k + 1 ) ( 4 + 1 )于是有偶数一 奇数( m o d 偶数) ，此乃矛盾故p = 4 k 即p 兰o ，证毕 由定理4 知，6 阶完全图k s 、p e t e r s v ”图p ( 5 ，2 ) 等都不是边优美 图 定理5 设g = ( y ，e ) 为( 户，q ) 图，且q 一户一1 ，“。，m 是g 中 7 不相邻的两顶点，若g 为边优美图，则添加图g + u 。”。也是边优美图 证明由g 为边优美图知，存在g 的边优美标号，：e ( g ) 一 1 ， 2 ，p 1 ) 使其诱导出的顶点标号，+ ：v ( g ) 一 0 ，1 ，户一1 为 双射，其中f + ( 口) 一2 5f ( u v ) ( r o o d 户) w t mj 扩张映射，为7 ；e ( g + “0 口。) 一 l ，2 ，p ) ， v 霎；兰。：g ，则7 为双射由7 诱导出的映 ( 0 。l ，p l 为 f ( u v ) “o ，7 3 i ) p + f ( w ) o p e ( g ， 即7 + ( 。) 一，。蓦 f ( u v ) ( r o o d 声) o “p e t 0 + h n 。n ) 因，+ ；v ( g ) 一( o ，l ，p l 为双射，故- i ：v ( g + “。u 。) 一 o ，1 ，声一1 亦为双射，于是7 为g + u o t ，。的边优美标号，g + u 。”。 为边优美图证毕 推论5 若丁是边优美树，e 苫e ( 丁) ，则添边图7 1 + e 是边优美单圈 图。 定理6 没g = ( y ，e ) 为( 户，口) 图且j f i q ，若g 为边优美图， 是g 的边优美标号，e 是g 中具有最大边标号q = f ( e ) 的边，则删边图 g e 也是边优美图 证明因g 是边优美图，f ：e ( g ) 一 1 ，2 ，q 是g 的边优 美标号，它使得导出映射，+ ：v 一 0 ，1 ，户一1 ) 为双射，其中，+ ( ”) ：，( “口) ( m o d 声) 记p ：郴j 0 限制映射，为三：e ( g - - e ) 一 1 ，2 ，q 一1 对于r ，e ( g e ) ，( e ，) 一f ( 。) 由f 为双射知也是双射由导出的映射 r 。 p 曲 0 0 归h j | g o v ，+ ； ， 射 + ：v ( g - - p ) 一 o ，1 ，p 一1 为 i f ( u v ) v ”。 一f + ( ”) 一( 州一f “ ( 。d 户) ”叫“1 l f ( u v ) 一q ”= u ot “f e l g ) pi q 一，( r )+ ( 口) 一，+ ( u ) ( r o o d 户) 由f + 为双射知 三+ 为双射，故g - - e 为边优美图证毕 由定理5 和定理6 知，”圈c 。与电路p 一的边优美性等价 3 2 几种常见囤类的边优美性特征 一些特殊图类的边优美性可由其顶点数来简明表征 定理7 ”圈c 。是边优美图当且仅当n 一1 ( m o d2 ) 证明必要性由3 1 巾推论2 即知 充分性：设c 。= 口l 虮矾u i ，v ( c 。) 一 即】，u 2 ，口。 ，e ( c 。) = 7 2 i + 。i i 一1 ，2 ，n ，下标取模 ，当n 一2 k 十1 时( ) ， 令，：e 一， 1 ，2 ，2 + 1 ) ，f ( u 。v + 。) 一i ，i 一1 ，2 ，2 + 1 显 然，是双射，导出映射+ 为： ，+ ( v i ) 一f u g k + 1 口1 ) + f ( v 1 口2 ) = ( 2 k + 1 ) 十1 ；1 ( m o d2 k + 1 ) ，+ ( ) = f ( v ，一1 口，) 十f ( v ， h 1 ) 一( i 1 ) 十i = 2 i 一1 ( i 一2 ，k ，k 十l ，2 女+ 1 ) 当2 i 时，+ ( ) = 2 i 一1 i 2 i 一1( m o d2 k + 1 ) 当k + 1 j 2 + 1 时，+ ( u 。) 一2 i l ；2 i 一1 一( 2 k + 1 ) 一2 ( i k 一1 ) ( m o d2 k + 1 ) 易知，+ ：y 一 0 ，1 ，2 k 为双射故奇圈c ：是边优美图 证毕 定理8n 个顶点的路p 是边优美图当且仅当”i 1 ( m o d2 ) 证明必要性由3 1 中推论l 即知 充分性由定理6 和定得7 即知或者，仿照c 。的边优美图标号直 9 接给出p + ，的边优美标号( 或边优美标号矩阵) 定理9 星图k 。是边优美图当且仅当n o ( r o o d2 ) 证明必要性由3 1 中推论1 即知 充分性：设v ( k l ， ) 一 口o ，口1 ，口。 ，e ( k 1 ， ) 一 v o v 。 i i 一1 ，n ) 当n 一2 k 时，令，：e 一 1 ，2 ，n ，( 口o ) 一i ， i 一1 ，2 ，n 双射，的导出映射，+ ：v 一 0 ，l ，n ) 为，+ ( 计) ：f ( v o v j ) 一i ，( 滓1 ，2 ，。) ，+ ( v o ) ；f ( v o v i ) 一浮虹掣型 一k ( n + 1 ) 10 ( r o o d ”+ 1 ) 因，+ 是双射，故k 。，口为边优美图证毕 定理1 0m 个n 圈c 的不交并m c 。边优美当且仅当m n = - - i ( m o d 2 ) 证明必要性：由3 1 中定理2 知p = m n 为奇数，从而m ，n 皆为奇 数充分性：记m c 。的点集y u v 。，v ，= “n ，“ ，边集 e u e ，e l = “；”“笄。l j 一1 ，2 ，n ) ( 此处约定“护一“，“肆。一“p ， 令，：e 一 1 ，2 ，n ，( m 1 ) + 1 ，m n ) ) ，( “j i ) l a 挥1 ) 一 ( ；一1 ) n + j i 一1 ，m ；j 一1 ，月则由双射，导出的映射，：v 一 0 ，1 ，2 ，3 ，m l l 一2 ，m n 一1 为 ，+ ( “j n ) 一f + ( “譬- “j i ) ) + f + ( “) f ( 2 1 1 ) n + 1j 一1 一 i ( 2 i 一1 ) ”+ 2 j 一1j 1 可以证明：当m ，n 为奇数时，f + 是双射，从而，是m c 。的边优美标号 事实上，可验证 f + ( “，) ，+ ( “ 1 ) ) ，f + ( “；f + ( 。f 字，) ，f + ( 。 2 ) ) ，1 广( “? ，) ；，十( “i m ，) ，+ ( “5 学，) ，广( 。兰)l f 1 ，3 ，2 n 一1 ；2 n + 1 ，2 n + 3 ，4 ”一1 ；5i 一【( m 1 ) h + 1 ，( m 1 ) ”十3 ，m n 一2 ) j 州nf 0 ，2 ，n 一1 ；n + l ，”+ 3 ，n + ( 2 n 1 ) ；。；l ；t i n 一( 2 n 一1 ) ，m n 一( 2 ，l 一3 ) ，m h 一1 )j 3 3 一类奇阶偶正则边优美图的构造 考虑正则图的边优美性时，不存在奇阶奇正则图由3 1 中推论4 知，偶阶偶正则图不会是边优美图对于偶阶奇正则图，广义p e t e r s e n 图 p ( ”，k ) 当n = - o ( m o d2 ) 且 詈时为边优美图，棱柱c 。鼠当n ； 0 ( m o d2 ) 时为边优美图啪】，k 。是边优美图，这验证了3 1 定理4 ( 2 ) 的结沦：偶阶边优美图的阶数必为4 的整数倍下面我们构造性证明了 一类奇阶偶正则图是边优美图 设c 。为n 圈，矿( c ) 一 t ，l 口2 ，v 。 ，e ( c 。) = 让口j i 一1 ，2 ， ，露) ( 必要时下标按模n 取余) 令c 表示如下图类( 2 a 昙) ： v ( c ) 一v ( c 。) 一 钉t ，副2 ，口。) e ( a ”) 一e ( c ) u 融+ i i 一1 ，2 ， ；下标取r o o dh 即c 是广义p e t e r s e n 图p ( 月，k ) 收缩n 条辐边后得到的n 阶4 正则连 通图显然，c 的顶点数p = n ，边数q = 2 p 且c 兰c ：”。 设2 女， z 詈，在c 的基础上又定义图类c p 、，t ，如下： v ( c i 1 i 。) = v ( c ) = p 1 ，u 2 ，u 。) e ( c 囊) 一y ( c 斗) u 研计+ 。i i = 1 ，2 ，”；m o d ” 则a - 。是一阶6 正则连通图 1 1 越。 丝 + ， 叼 中 “ q o 0 ， 芹 “ n “ 0 ，h 宁 孚宁 o 广 广 学中字 n 一般地可类似构造更高度数的偶正则连通图c 黟。4 r - ，其中2 - 。 ， 詈，易知，c z ，t 的顶点数p = n ，边数为g 一( r + 1 ) p ， 且为2 ( r + 1 ) 度正则图 定理1 1当( 2 ( r + 1 ) ，2 m + 1 ) 一l 时，奇阶2 ( r + 1 ) 正则图 c 2 ( 卅k l , + k 2 1 , ( 其中2 kj k 2 五， 掣) 是边优美图 证明记户一2 m + 1 ，g 一( r + 1 ) p 令，：e 一 1 ，2 ，g 如下： f ( v l v i + 1 ) 一i ，f ( v i v i + k 。) 一p 十i ，厂( 7 j i v i + k 2 ) 一2 p + i ， f ( v l v i + i ) 一r 户+ i ，i 一1 ，2 ，p 则双射，导出的映射，+ ：y 一 o ，1 ，户一l 为 ，+ ( 口：) 一三f ( u v ，) “ e = f ( v 一- 口r ) + f ( v t ”，+ ) + f ( v i - - h t ”) + f ( v ，口；+ 1 ) + f ( v i - - k 2 v 。) + f ( v l v i + , t 。) + + f ( v i 一，口：) + f ( v ，口。+ ) 一( i 一1 ) + i + ( 户+ i k 1 ) + ( 户+ i ) + ( 2 p + i 一 2 ) + ( 2 p + i ) + + ( r p + i 一 ，) + ( r p + i ) 一2 p ( 1 + 2 + + r ) + 2 ( r + 1 ) i 一( l + k 2 + + k ，+ 1 ) 一2 ( r + 1 ) i 一( 互 j + 1 ) ( r o o d 户) i 一1 ，2 ，p 因为( 2 ( r + 1 ) ，2 r e + 1 ) = 1 及1 ，2 ，p 是模p 的一个完全剩 余系，由上节中引理1 知f - ( 。) 一2 ( ，+ 1 ) i 一( 圭 ，+ 1 ) ，( 净1 ，2 ， j = 1 。 ，户) 也是模p 的完全剩余系，故f + 为双射从而，c ：齿是奇阶 偶正则边优美图，证毕 取r = m - - 1 有c ；鬻一一k 。， 故得 推论6 奇阶完全图k ：。+ 。都是边优美图 1 2 上述构造的奇阶偶正则图的边优美标号并不唯一，例如有： 定理1 2当( 3 ，2 m 十1 ) 一1 时，奇阶4 正则图c ：+ 1 ( 2 2 ) 的两个悬挂点分别与奇数个新点相连， 各个内点分别与偶数个新点相连所得的一类毛虫树为边优美树 为了研究完全奇元树的边优美性，需要建立如下引理： 引理2 奇阶根树的奇( 偶) 分枝点个数为偶( 奇) 数 证明设g 一( y ，e ) 为奇阶根树且阶数为户，边数为q = p - - 1 则 。酽。( ”) 一g 一。s ，d + ( ”) 由。酽+ ( ”) 一偶数知，出次为奇数的顶点 个数为偶数 引理3 对于前6 ( e ) 个自然数的集合s 一 1 ，2 ，3 ，6 女 - - 2 ，6 一1 ，6 ) ，存在模6 + 1 的分划d 一 s ，s i 。， s 。t ) 且每个分划块含有3 个数 证明： 1 4o 令s i 一 1 ，k + 1 ，5 k 一1 ) s 2 一 2 ，k + 2 ，5 k 一3 ) s 3 = 3 ，k + 3 ，5 k 一5 s 。一 k ，2 k ，3 k + 1 易验证s 。n s ，= i j 2 k + 1 ，5 k ，5 女+ 1 ) 2 + 2 ，5 一2 ，5 k + 2 2 k 十3 ，5 一4 ，5 自+ 3 ) 3 ，3 + 2 ，6 ) s 互z ；o ( r o o d6 k + 1 ) 定理1 4 奇阶完全3 元树都是边优美树 证明由引理2 知，奇阶完全3 元树7 t 的分枝点( 均为奇分枝点) 个 数为偶数，设为2 ( ) ，并且顶点数p 一6 k + 1 ，边数q 一6 k 现规定丁的边标号，：e 一 1 ，2 ，q ) 如下： 将引理3 中的s 一 1 ，2 ，3 ，q 一2 ，q 一1 ，q 的2 个模p 分 划块s ，( i 一1 ，k ，k + 1 ，2 k ) 中的3 个数依次给第i 个分枝点口。 ( i 一1 ，k ，k + 1 ，2 k ) 的出边标号，易见，是双射 由于每个分划块s ，中元素之和是声一6 + 1 的倍数，所以在模p 同 余意义下，导出的顶点”v 的标号恰为其父顶点”与它相连的边”v 的标号零级顶点的标号是。一声( r o o dp ) 故，+ ：y 一 0 ，1 ，2 ， p 一1 ) 为双射即，是7 的边优美标号证毕 完全3 元树的点迁树可能是广义完全偶元树，也可能是广义完全奇 元树，还可能是奇偶交错元树 推论8 奇阶完全3 元树的点迁树是边优美树 推论9 奇阶完全3 元树的点迁树的模p 局部点迁树是边优美树 例1 奇阶完全3 元树及其点迁树和模p 局部点迁树的边优美标号 = = = n 殳 沁渐一 。叭。 图1 避优美树t图2 t 的点迁树t 垒l 蠲3 t 的禳龋部廉迁树l ，u 。v 。强4 冀瀚另一模p 局部点遥树l ，u 。v 。 奇阶完全3 元树的边优荧性可推广到一般的奇阶完众奇元树 号l 理4 对数集s 一 1 ，2 ，3 ，2 ( 2 n + 1 ) 一1 ，2 k ( 2 n + 1 ) ( ，h n ) ，存在模p = 2 k ( 2 n + 1 ) + l 的分翔d 一 s ，& ，函+ ， s z t ) ，且每个分划块s 。中恰有2 n 十1 个元素 证明当h l 时，由引壤3 即知 下谈n 2 。记 s 1 一 1 ，l + 1 ，5 k 一1 ，6 j + 1 ，8 k ，1 0 k + 1 ，1 2 k - ，( 4 n 一2 ) k + 1 ，4 n k s 2 = 2 ，k + 2 ，5 一3 ，融+ 2 ，8 k 一1 ，1 0 k + 2 。1 艚一1 ，( 4 n 一2 ) + 2 ，t n 一1 s 3 = 3 ，矗+ 3 ，强一5 ，强+ 3 ，赫2 ，1 0 k + 3 ，1 糖一2 ，( 4 n 一2 ) k + 3 ，4 n k 一2 s k 一 ，2 。强十1 ，7 k ，7 h + 1 ，l l k 。i l k + 1 ，( 4 n 1 ) ，( 4 n 一1 ) k + 1 1 6 s i + 1 = 2 + 1 ，5 k 5 k + 1 9 k ，9 k + 1 1 3 k ，1 3 k + 1 ，t ( i n + 1 ) k ，( 4 n + 1 ) k + 1 s + 2 ： 2 + 2 ，5 k 一2 ，5 k 十2 ，9 k 一1 ，9 k + 2 1 3 1 1 ，1 3 k + 2 ，( 4 月+ 1 ) 1 1 ，( 4 n + 1 ) k + 2 s + ：= 2 + 3 5 k 一4 ，5 + 3 ，9 k 一2 ，9 k + 3 ，1 3 k 一2 ，1 3 k + 3 ，( 枷+ 1 ) k 一2 ，( 4 n + 1 ) k + 3 s h = 赫3 + 2 6 鼬+ 1 ，l o k 1 趾+ l ，1 4 k ，4 柚+ 1 ，( 4 + 2 ) k 易证：s 。n s ，一黟( i j ) u s ，一s 每个s i 中含2 n + 1 个元素，且= z o( m o d6 6 + 1 ) ：5 此处仅选s 。和s 。加以验证事实上， ，主z = 1 + ( + 1 ) 十( 5 一1 ) + 三 ( 4 i 一2 ) k + 1 十4 i k ： o ，= ， ( 6 + 1 ) + 8 k 兰i 一( 2 k 1 ) ( n 一1 ) i = 2 = ( 6 女+ 1 ) + 8 k 半一1 一( 2 k 一1 ) n + ( 2 k 一1 ) 一( 4 k n + 2 k + 1 ) ” = o ( r o o d2 ( 2 n 十1 ) + 1 且s ，中共有3 + ( n 一1 ) + ( n - - 1 ) 一2 n + 1 个元素 ，享z 一 ( 2 + 1 ) + 5 k + ( 5 + 1 ) + 。t o + 1 。2 ：2 ( 4 i + 1 ) k + ( 4 i + 1 ) + 1 ) 一( 1 2 k + 2 ) + 8 kk i + 兰( 2 k + 1 ) i = 2i = z = ( 1 2 k + 2 ) + s k i 半一1 ( 2 + 1 ) ( ”1 ) 一( 4 k n + 2 k + 1 ) ( n + 1 ) e0 ( r o o d 2 k ( 2 n + 1 ) + 1 ) 且& + - 中含有3 + 2 ( ”一1 ) = 2 n + 1 个元素证毕 1 7 定理1 5 奇阶完全奇元树都是边优美树 证明由引理2 知，奇阶完全( 2 n + 1 ) 元树7 的分枝点( 均为奇分 枝点) 个数为偶数，设为2 ( ) ，并且丁的边数口一2 k ( 2 ”+ 1 ) ，顶 点数声一2 ( 2 n + 1 ) + 1 当n 一1 时，定理1 4 已证 当n 2 时，由引理4 知，数集s 一 1 ，2 ，q 存在分划d 一 ( s 。，s l ，s ，s ：t ) ，其中每个模p 分划块s 。恰含2 n + 1 个 元素由此可规定7 的边标号，：e 一 1 ，2 ，q ) 如下： 将丁的2 个奇分枝点编号为口。，。”t ，v h 。，_ 。t ，给”。的2 n + 1 条出边按对应的分划块中的2 n + 1 个数分别标号，易见，：e 一 ( 1 ，2 ，q ) 为双射 由于每个s ，是模p 的分划块即s 。中元素之和是p = 2 k ( 2 n + 1 ) + 1 的倍数，故由边标号，导出的顶点”y 的标号( 在模p 的同余的意义 下) 恰好是其父顶点u 与。相连的边u v 的标号零级顶点的标号是p 一 0 ( r o o d 户) 故，+ ：y 一 0 ，1 ，2 ，户1 为双射，于是，是丁的边 优美标号证毕 推论1 0 奇阶完全奇( 或偶) 元树的点迁树是边优美树 推论1 1 奇阶完全奇( 或偶) 元树的点迁树的模p 局部点迁树仍是 边优美树( 户为树的阶数) 推论1 2 p 阶边优美树的模p ( 局部) 点迁树还是边优美树 虽然由奇阶完全奇元树的点迁树及其局部点迁树可以得到某些奇偶 交错元树的边优美性，但是为了直接讨论奇偶元树的边优美性，我们特建 立如下两个引理： 引理5 对数集s 一( 1 ，2 ，3 ，2 女+ 6 n )( ，”z + ，k ，” 不同时为，o ) ，存在模户一2 + 6 n 十1 的分划d - - ( s l ”，5 掣，s 1 2 ) ， 酬” 使得每个分划块s 户为3 元数集( 净1 ，2 n ) ，每个分划块s j 2 ) 1 8 为2 元数集( j 一1 ， ) 证明先将s 中的数按 l 2 ”n + 1 k 十”+ lk + + 2 k + 2 nk + 2 n + 1 k + 3 n + 1k + 3 n + 2 k + 4 nk + 4 n + 1 5 n + k + 15 n + k + 2 5 + 2 女2 女+ 孙+ 1 再令 s 算。 5 挥2 s 算3 s 掣 5 ( 3 ) 一 1 ， 5 ；3 ) 一 2 ， 5 ；3 ) 一 3 ， k 十h + 1 ， k + n 十2 ， k + n + 3 ， 小到大排列如下 月+ k 1 月+ k k + 3 n 一1 ，k + 3 n k + 5 n 一1 ，女+ 5 n 2 屉+ 6 n 一1 ，2 五+ 6 n k + 5 n 一1 k + 5 n 一3 k 十如5 s 一( m ，k 十2 n ，k + 3 n + 1 k 十2 n + l ， ( k + 2 n + 2 ， f k + 2 n + 3 ， k + 3 n ， k _ 一5 n ， k + 5 n 2 k + 5 n 4 ， 2 + 5 n + 1 ) 2 十5 n + 2 2 + 勋+ 3 k + 3 n + 2 ，2 k + 6 n f s 2 一 月+ l ，5 n + 2 k i s l ”一f n + 2 ，5 + 2 k 一1 5 ；2 一 n + 3 ，5 n + 2 k 一2 ) 卜” l s l 2 一 月+ k ，5 n + k + 1 不难验证s 的上述分划d 满足要求 注：当k = 0 时，分划d 中不含砖2 ( 参见引理3 ) ；当。一。时，d 中 不含5 f ” 引理6 设具有p 个顶点和q 条边的根树t 中没有出度为1 的奇分 枝点，丁中奇分枝点的个数为m ，则t = ( v ，e ) 的边集e 可分成m 个 子集e ”和k 个子集日”的不交并，使得每个边组e f 3 ( 滓1 ，2 ， m ) 恰含第i 个奇分枝点的3 条出边，每个边组e ；2 ( ，一1 ，) 恰含 某分枝点的2 条出边，其中 一q - - 。3 m 证明因为根树丁任一顶点的出度都不为1 ，所以除叶点之外，每个 分枝点”的出度d + ( ”) 2 ( 1 ) 若d + ( 口) 一2 a ( n e ) 为偶数，则可将”的2 口条出边分成n 组e i ”，e ”，每组恰含7 3 的两条出边 ( 2 ) 若d + ( ) 2 6 + 3 为奇数( b e z + ) ，则可将口的2 6 + 3 条出边 分成6 + 1 组e “，e i ”，e 铲，其中e ”恰含奇分枝点u 的3 条出边， e ”，e ；”各含v 的两条出边这样根树了的边集( 视为所有顶点的 出边的集合) 可分成m 个3 元子集e ；3 ( i l ，2 ，m ) 和k 个2 元子 集目2 1 ( j 一1 ，2 ， ) 的不交并 记v = v o u v 。u v z ，其中y o 是偶分枝点的集合，v 。是出次为3 的奇 分技点集合，n 是出次大于3 的奇分枝点集合，则 q 一蓦d + ( 口) 一d + ( ”) + d + ( ”) + d + ( 口) 口y 口y n口y 1# y 。 一d + ( 口) + 3 十( d + ( 。) 一3 ) 9 y o 。r l u y 。y 2 一d + o ) + 3 m + ( d + ( ”) 3 ) 。p o r 2 故e 一崆9 证毕 注：特别地，当根树丁不含奇分枝点时，e ；3 的个数为0 ；当根树丁 为完全3 元树时，e j 2 的个数为0 定理1 6 不含2 度顶点的奄阶树都是边优美树 证醪设。怒夺舍2 度强患静奇阶楗? 、一( 矿，昱) 中麴任一； 辩l l 点，以7 为基穑翻得到一棵l 冀”。为根醣掇礴t ，则d “ 1 ，对vu v ， 计o 由d 一( ) = 1 且d + ( z ，) 2 知，d + ( 钉) = d ( ”) - - d 一( 口) 一矗( v ) 一1 1 。故根树中每个顶点懿蹬度不为1 由g 理2 翔，奇跨根祷妒的奇分技点个数为缡数，设为2 n ( ，：z + ) ， 由引理6 知，可将t ，_ ( y ，e ) 的边集分成2 n 个子集觑j ”( i 一1 ， 2 n ) 秘女一望二警个子集e 甲，麟。的不交势￥一l 荭l = 2 k - - 6 n ，声一 v | 一2 女+ 6 h + 1 ， 记v 一 o ，w l ，口2 ， 潍+ 6 。) e 一 p 1 ，e 2 ，e 2 t 5 。 一一e ”u u e g u e ”u u e ”。冀嘻 麓顶点功弱入逸( ；一1 ，2 ，。2 女+ 6 n ) 再由引理5 知，数集s 一 1 2 ，2 女十6 ，一 可分成2 ”个3 元予 集s ；3 ( i 一1 ，2 n ) 和 个2 元子集s 尹( ，一1 ，k ) 的不交并 鬻s 一 1 ，2 ，2 女+ 6 ” 一s ；”u u s 留u s i ”u u 掰” 令双射，：e s 使得，：e j ”一s j ”，；蟛2 一硝2 为双射( 净】， ，2 n # ，一1 ，t 女) 则由，导出的顶点标号厂：矿一 o ，1 ，2 ， 2 女+ 锄 瀵霆； f + ( o ) 一2 _ ，( 口o ”) i 2 + 6 n + l _ o ( z o d2 k + 6 n + 1 ) v n q 让。，- 厂+ ( f ，) = ，( _ ，舟) + ，( b ) 勰厂( 竹) ( r o o d2 k + 6 越+ i ) “一l 敖f + ：v 一 昝o ，耵l ，口2 ，z r 2 t + g n 斗 o ，1 ，2 ，2 k + 6 玎 为双射 即，是树7 亦即树7 1 的边优美标号证毕 推论1 3 只含唯个2 度顶点的奇除瓣是边优美树+ 滚鹾设奄除褥? 中翼含嚷一酶2 菠颈患。，受l 戮7 为基础蹬以。 为根可得根树了”在丁中，d + ( ”。) 一d 。 。) = 2 v 口v ，”。，删 - 2 l d 一( 口) 一1 且d ( 口) 2 ，于是d + ( 口) 一do ) - - d o ) 一d ( 口) 1 1 故根树7 1 中无出度为1 的顶点由定理1 6 知，7 为边优美树，且丁的边 优美标号可按定理1 6 中方法进行证毕 例2 含2 度顶点个数1 的奇阶树的边优美标号 v 4v 5v 6 v 7v b 图5 2 2 囝6 4 问题与猜想 图的边优美性这个新课题中有许多问题有待于进一步研究一般来 讲，对于给定的一个( 户，口) 图g = ( y ，e ) ，欲判明g 的边优美性，需 要考察q ! 个双射，：e 一 1 ，2 ，q 及其导出映射，+ ：y 一 0 ，1 ， ，声一1 是否为双射，计算量相当大无论是肯定还是否定g 的边优美 性，往往都不容易这正是边优美图研究的困难所在本文前面讨论了 边优美图的必要条件，但满足必要条件的这些图在什么条件下一定是边 优美的呢? 作为边优美图课题的基本问题，我们提出： 问题1 表征边优美图，即给出边优美图的充分必要条件 问题1 的解决估计是十分困难的即使是对一些特殊图类给出其边 优美性特征也未必轻而易举寻求图的边优美标号和寻求图的点优美标 号、协调标号等一样，目前也主要囿于一些特殊图类这也符合从特殊到 一般的认识规律事实上，许多特殊图类的边优美性答案仍然是谜因 此，下述问题也是有价值的： 问题2 讨论特殊图类( 如完全二部图k 等) 的边优美性 问题3 进一步讨论奇阶偶正则图和4 m 阶奇正则图的边优美性 从研究边优美图的方法或工具来看，本文中涉及到的方法可归类为： 试探法：主要对一些特殊图类给出优美标号；解同余方程组方法：通 过求同余方程组，+ ( 口，) p b 。( 卢o ，l ，户一1 ) 的特解得到边优美标 号，；边标号矩阵法：用矩阵方法验证边标号是否为边优美标号；运 算法：如添边法、删边法；构造法：构