图P_m_C_n和W_m_n_的序列性

图P_m_C_n和W_m_n_的序列性 () 图 ×和, 的序列性m n PCW m n 1, 2 1刘春峰, 朱振广 ( ) 1. 辽宁工学院 数理系, 辽宁 锦州 121001 ( )2. 锦州市教育局, 辽宁 锦州 121000 () () () (摘要: 给出了图 P× C , I P × C 和W m , n 的序列标号. 证明了图 P × C , I P× C 和W m ,m n m n m n m n ) () nm Ε 1, n Ε 3 且 n 为奇数是序列图, 从而也是调和图. 关键词: 优美图; 序列图; 顶点标号 1 引言及主要结果 图的标号理论在编码、雷达、通信网络、射电天文学等方面均有广泛的应用. 本文主要研 () () ) (究了三类图 P × C , I P × C 和W m , n 的序列标号. 文中 G = V , E 表示一个顶点m n m n 集为V , 边集为 E 且没有孤立点的简单图. 文中没有提及的术语参见1 . ) ( ) ( 定义 称图 G = A , B 是序列图 sequ en t ia l g rap h , 如果存在一个单射, () Η: V G ? {0, 1, 2, , E - 1} || () 如果 G 是树, 则也包含 | E | 使的由 () () ()Ηu v = Ηu + Ηv () 所导出的函数对所有的边 e = u v ? E G , 其映射 () E G ? {c, c + 1, , c + E - 1}|| () 是一个双射 其中 c 为某一非负整数. 称 Η为 G 的一个序列标号. () () () () ( () 在定义中的单射 Η, 若使函数 Η″u v = Ηu + Ηv m o d E 对 u v ? E G 为边集||() E G ? {0, 1, 2, , E - 1} 的双射, 则称 Η为 G 的一个调和标号. 称 G 为调和图.|| 由定义 2 可以看出, 若把图的序列标号对边数| | }取摸, 就得到了该图的调和标号, 即 E 序列标号只是调和标号的特殊情况. 2 P 和C 分别是m 个点的路和 n 个点的圈. 积图P ×C , 实际上是由m 个长度为 n 互 m n m n i i i i i i+ 1 ) ( )( 不相交的圈 C = x , x , , x , i = 1, , m 加上边 x x i = 1, , m - 1, j = 1, , n n 1 2 n j j m m () 所组成的图. 蛛网图是 P m × C n 中在 C上的每个点都加一条悬挂边 x y i 1 Φ i Φ n , 且有n i 1 () ()一点 x | V P × C , x 与 C 的每个点都相连所得到的图, 记作W m , n . 图 G 的冠是在0 m n 0 n ()G 上的每个点都加一条悬挂边所得到的图, 记作 I G . —4 2 . 本文讨论当 n 为奇数时, 图 P 关于 P m ×C n 优美性问题国内外学者作了许多研究m () () × C 的序列性, 并给出了 I P × C 和W m , n 的序列标号. 得到了如下结果.n m n 定理 1 若m Ε 1, n Ε 3 且 n 为奇数, 则 P × C 是序列图.m n () 定理 2 若m Ε 1, n Ε 3 且 n 为奇数, 则 I P × C 是序列图.m n () 定理 3 若m Ε 1, n Ε 3 且 n 为奇数, 则W m , n 是序列图. () () 推论 若m Ε 1, n Ε 3 且 n 为奇数, 则图 P ×C , I P ×C 和W m , n 是调和图.m n m n 2 定理的证明 2. 1 定理 1 的证明 () () 在图 P × C 中, V P ×C = m n , E P ×C = 2m n - n. 定义 P ×C 的顶 || || m n m n m n m n 点标号 Η如下: () i + j n - n - 1, 1 Φ i Φ n + 12, 1 Φ j Φ m 且 j 为奇数, ƒj () Ηx =i- 1 2 (() ) i + j n - 1 - n + 12, 1 Φ i Φ n + 12, 1 Φ j Φ m 且 j 为偶数,ƒƒ (() ) i + j n - n + 1ƒ2, 1 Φ i Φ n - 1ƒ2, 1 Φ j Φ m 且 j 为奇数,j () Ηx =i 2 () i + j n - 1 - n , 1 Φ i Φ n - 12, 1 Φ j Φ m 且 j 为偶数.ƒ 下面验证 Η是 P × C 的序列标号. 设m n j() A = {Ηx | i = 1, 2, , n }, j = 1, 2, , m . j i 有 1 1 () () () () A = {Η= 1, 2, , n + 12} ? {Η= 1, 2, , n - 12}ƒƒ1 x i- 1 | i x i | i 2 2 () () () = { i - 1 i = 1, 2, , n + 12} ? { i + n - 12 i = 1, 2, , n - 12} |ƒƒ|ƒ() () = {0, 1, , n - 12} ? { n - 12 + 1, , n - 1}ƒƒ () () = {0, 1, , n - 1ƒ2, n - 1ƒ2 + 1, , n - 1}, 2 2 () () () () A = {Ηx | i = 1, 2, , n - 1ƒ2} ? {Ηx | i = 1, 2, , n + 1ƒ2}2 i i- 1 2 2 () () () = { i + n - 1| i = 1, 2, , n - 1ƒ2} ? { i + n - 1ƒ2| i = 1, 2, , n + 1ƒ2} () () = {n , n + 1, , 3 n - 1ƒ2} ? {3 n - 1ƒ2 + 1, , 2n - 1} () () = {n , n + 1, , 3 n - 12, 3 n - 12 + 1, , 2n - 1}, ƒƒ 当m 为奇数时, 有 m - 1m - 1() ( ) ( ) ( ) A = {Ηx i = 1, 2, ,n - 12} ? {Η x i = 1, 2, ,n + 12}| ƒ| ƒm - 1 2 i 2 i- 1 () = { i + m n - 2n - 1 i = 1, 2, , n - 12} ? |ƒ () () { i + m n - 3n + 1ƒ2| i = 1, 2, , n + 1ƒ2} () () = {m n - 2n , , m n - 3 n + 1ƒ2} ? {m n - 3 n + 1ƒ2 + 1, , m n - n - 1} () () = {m n - 2n , , m n - 3 n + 1ƒ2, m n - 3 n + 1ƒ2 + 1, , m n - n - 1}, mm() () () () A = {Ηx | i = 1, 2, , n + 1ƒ2} ? {Ηx | i = 1, 2, , n - 1ƒ2}m i- 1 i 2 2 () = { i + m n - n - 1| i = 1, 2, , n + 1ƒ2} ? () () { i + m n - n + 12 i = 1, 2, , n - 12} ƒ|ƒ () () = {m n - n , , m n - n + 1ƒ2} ? {m n - n + 1ƒ2 + 1, , m n - 1} () () = {m n - n , , m n - n + 12, m n - n + 12 + 1, , m n - 1}. ƒƒ 当m 为偶数时, 有 m - 1m - 1() ( ) ( ) ( ) A = {Ηx 2 i- 1 i = 1, 2, ,n + 12} ? {Η x 2 i i = 1, 2, ,n - 12}| ƒ| ƒm - 1 () = { i + m n - 2n - 1| i = 1, 2, , n + 1ƒ2} ? () () { i + m n - 3n + 12| i = 1, 2, , n - 12} ƒƒ () () = {m n - 2n , , m n - 3n + 12} ? {m n - 3n + 12 + 1, , m n - n - 1} ƒƒ () () = {m n - 2n , , m n - 3n + 1ƒ2, m n - 3n + 1ƒ2 + 1, , m n - n - 1}, mm() () () () x i = 1, 2, , n - 12} ? {Ηx i = 1, 2, , n + 12}A = {Η| | ƒƒm i i- 1 2 2 () = { i + m n - n - 1| i = 1, 2, , n - 1ƒ2} ? () () { i + m n - n + 32 i = 1, 2, , n + 12} ƒ|ƒ () () = {m n - n , , m n - n + 3ƒ2} ? {m n - n + 3ƒ2 + 1, , m n - 1}.j () 由于A = {Ηx i = 1, 2, , n , j = 1, 2, , m } = A ?A ? ?A = {0, 1, , m n| i 1 2 m () () () () - 1}, |A | = |V P × C | , 于是得, Π u , v ?V P × C , 若 u ? v , 有 Ηu ? Ηv 且m n m n () m in A = 0, m ax A = m n - 1 < 2m n - n = E P × C .||m n 设 0 j j() () = {Ηx + Ηx i = 1, 2, , n }, j = 1, 2, , m , | D j i i+ 1 1 jj + 1() () D = {Ηx + Ηx i = 1, 2, , n }, j = 1, 2, , m - 1, | j i i j j 其中 x + 1 = x , j = 1, 2, , m . 有n 1 0 1 1 1 1() () () () D = {Ηx + Ηx } ? {Ηx + Ηx | i = 1, 2, , n - 1} 1 n 1 i i+ 1 () () () () = { n - 1ƒ2} ? { n + 1ƒ2, n - 1ƒ2 + 1, , 3 n - 1ƒ2} () () () = { n - 1ƒ2, n - 1ƒ2 + 1, , 3 n - 1ƒ2}, 1 1 2() () = {Ηx + Ηx | i = 1, 2, , n } D 1 i i () () () = {3 n - 1ƒ2 + 1, 3n - 1ƒ2 + 2, , 5n - 3ƒ2}, 0 2 2() () = {Ηx + Ηx i = 1, 2, , n } | D 2 i i+ 1 () () () = { 5n - 32 + 1, 5n - 32 + 2, , 7n - 32}, ƒƒƒ 1 2 3() () = {Ηx + Ηx | i = 1, 2, , n } D 2 i i () () () = { 7n - 3ƒ2 + 1, 7n - 3ƒ2 + 2, , 3 3n - 1ƒ2}, 当m 为奇数时, 有 0 m - 1m - 1m - 1m - 1() () () () = {+ }?{+ | = 1, 2, , - 1}m - 1 Ηx n Ηx 1 Ηx i Ηx i+ 1 in D () () () = {2- 7+ 1ƒ2}?{2- 7+ 1ƒ2+ 1, , 2- 5+ 3ƒ2},m n n m n n m n n 1 m - 1 m() () = {+ = 1, 2, , }| m - 1 Ηx i Ηx i in D () () = {2- 5+ 32+ 1, , 2- 3 + 12}, ƒƒm n n m n n 0 m - 1m - 1() () = {+ | = 1, 2, , }D m Ηx i Ηx i+ 1 in () () () = {2- 3 + 1ƒ2+ 1, 2- 3 + 1ƒ2+ 2, , - 1ƒ2+ 2- - 1}.m n n m n n n m n n 当m 为偶数时, 有 0 m - 1m - 1() () = {+ | = 1, 2, , }D m - 1 Ηx i Ηx i+ 1 in () () () = {2- 7+ 12, 2- 7+ 12+ 1, , 2- 5+ 32} ƒƒƒm n n m n n m n n 1 m - 1 m() () = {+ | = 1, 2, , }m - 1 Ηx i Ηx i in D () () = {2- 5+ 32+ 1, , 2- 3 + 12}, ƒƒm n n m n n 0 m - 1m - 1 m m() () () () = {+ }?{+ | = 1, 2, , - 1}D m Ηx n Ηx 1 Ηx i Ηx i+ 1 in () () () = {2m n - 3 n + 12+ 1}?{2m n - 3 n + 12+ 2, , n - 12+ 2m n - n - 1}.ƒƒƒ 0 1 0 1 0 ) () (() () 由于D = D ?D ? ? D ?D ?D = { n - 12, n - 12 + 1, ,ƒƒ- 1 - 1 1 1 m m m (() () ) n - 12 + 2m n - n - 1}, D = E P ×C , 于是得 Π e, f ? E P ×C , 若 e ? f ,ƒ|| ||m n m n () () () 有 Η′e? Η′f , 即 P × C 中不同的边标号不同, 且m in D = n - 1ƒ2, m ax D Φ 2m nm n () - n = | E P × C |. 由序列图的定义得 P × C 为序列图.m n m n 2. 2 定理 2 的证明i () ( () ) ( () ) 在图 I P ×C 中, V I P ×C = 2m n , E I P ×C = 3m n - n. 设与 x 相| || m n m n m n j i ( )() 连的一度点为 y i = 1, , m , j = 1, , n . 定义 I P × C 的顶点标号 Η如下:m n j j Φ m 且 j 为奇数, () 1 Φ i Φ n + 1ƒ2, 1 Φ i + j n - 1 - n , j () Ηx i- 1 =2 () ) ( 12, 1 Φ i Φ n + 12, 1 Φ ƒƒi + j n - 1 - n + j Φ m 且 j 为偶数, (() ) i + j n - n + 1ƒ2, 1 Φ i Φ n - 1ƒ2, 1 Φ j Φ m 且 j 为奇数, j () Ηx =i 2 () i + j n - 1 - n , 1 Φ i Φ n - 12, 1 Φ j Φ m 且 j 为偶数, ƒ j j () () () Ηy = 3m n - n + 3ƒ2 - Ηx + i - j n , 1 Φ i Φ n , 1 Φ j Φ m .i i () 可与定理 1 的证明类似验证 Η是W m , n 的序列标号. 2. 3 定理 3 的证明 () (() ) () ()在图W m , n 中, V W m , n = m n + 1, E P ×C = 2m n + n. 定义W m , n || || m n 的顶点标号 Η如下: () () Ηx = 2m n + n - 1ƒ2,0 () i + j n - 1 - n , 1 Φ i Φ n + 12, 1 Φ j Φ m 且 j 为奇数,ƒj () Ηx = 2 i- 1 (() ) i + j n - 1 - n + 1ƒ2, 1 Φ i Φ n + 1ƒ2, 1 Φ j Φ m 且 j 为偶数, (() ) i + j n - n + 1ƒ2, 1 Φ i Φ n - 1ƒ2, 1 Φ j Φ m 且 j 为奇数, j () Ηx = () i i + j n - 1 - n , 1 Φ i Φ n - 12, 1 Φ j Φ m 且 j 为偶数, ƒ2 (() ) i + m n + n - 32, 1 Φ i Φ n + 12, 且m 为奇数, ƒƒ () i + m n - 1, 1 Φ i Φ n + 1ƒ2, 且m 为偶数, () Ηy = 2 i- 1 () i + m n - 1, 1 Φ i Φ n - 12, 且m 为奇数, ƒ (() ) i + m n + n - 1ƒ2, 1 Φ i Φ n - 1ƒ2, 且m 为偶数. () Ηy =2 i () 可与定理 1 的证明类似验证 Η是W m , n 的序列标号. () 图 1 P × C 及其序列标号 图 2 图 I P × C 及其序列标号3 5 2 5 () 图 3 图4 图 P 2 × C 7 及其序列标号W 2, 5及其序列标号 图 参考文献: 1 马克杰. 优美图[. 北京: 北京大学出版社, 1991.M ( ) 2 杨燕昌, 王广选. 积图 C × P 的优美性[J . 数学研究与评论, 1995, 15 2: 66—71.4n+ 2 4k + 3 : , [. , 1989,3 . Ga llian J AA su rveyrecen t re su lt sco n jec tu re s and op en p ro b lem s in labe ling g rap h s J J G rap h T h eo ry ( ) 13 4: 491—504. ( ) 4 . [ . , 1994, 49: 213—229.Ga llian J AA gu ide to th e g rap h labe ling zoo J D isc re te A pp l M a th ()m ×n , On Sequen t ia l of PCan d W m n 1, 2 12, 2L IU C h u n fen gZHU Zh en gu an g () 1. , , 121001, D ep a r tm en t o f M a th em a t ica l Sc ienceL iao n ing In st iu te o f T ech no lo gyJ inzho u C h ina ()2. , 121000, J inzho u E duca t io n B u reauJ inzho u C h ina () ()P × C , I P × C and W m , n . : A bstrac tW e o b ta in th e sequen t ia l labe ling fo r g rap h s m n m n It () () () P × C , I P × C and W m , n m Ε 1, n Ε 3 is p ro ved th a t m n m n and n is o dd is sequen t ia l , .g rap h sth ey a re a lso h a rm o n io u s : ; ; Keywordsg racefu l g rap hsequen t ia l g rap hve r tex labe lling