PM  >> Vol. 8 No. 6 (November 2018)

作者:  

刘春峰:辽宁工业大学数理系,辽宁 锦州

关键词:
优美图序列图顶点标号Graceful Graph Sequential Graph Vertex Labelling

摘要:

G的标号是指G的顶点集到一个整数集的映射g,且对e=uv∈E(G)由g(u)g(v)诱导出边e的标号。本文给出了链路Pn(m)的k-优美性和序列性。即证明了图Pn(m)是k-优美图和序列图,从而也是调和图。进而推广了原有的一些结果。

The labelling of a graph G is injection g of the labels of vertices to a set of integers, and the labels of each edge e= uv are induced by the g(u) and g(v). In the paper, the k-gracefulness and sequence of graphs are given, and we also prove Pn(m) graph is k-graceful, sequential, and harmonious.

1. 引言及主要结果

图的标号理论在编码﹑雷达﹑通信网络﹑射电天文学等方面均有广泛的应用。本文主要研究由路Pn构造的图Pn(m)的k-优美标号和序列标号。文中 G = ( V , E ) 表示一个顶点集为V,边集为E且没有孤立点的简单图。文中未提及的术语见 [1]。

定义1:称图 G = ( A , B ) 是k-优美(k-graceful)图,如果对任何正整数k,

f : V ( G ) { 0 , 1 , 2 , , | E | + k 1 }

使的由

f ( u v ) = | f ( u ) f ( v ) |

所导出的函数对所有的边 e = u v E ( G ) ,其映射

E ( G ) { k , k + 1 , , k + | E | 1 }

是一个双射。称f为G的一个k-优美标号。显然k-优美图,当k = 1时,就是通常所说的优美图。

定义2:称图 G = ( A , B ) 是序列图(sequential graph),如果存在一个单射,

θ : 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的一个序列标号。

在定义2中的单射 θ ,若使函数 θ ( u v ) = θ ( u ) + θ ( v ) ( mod | E | ) (对 u v E ( G ) 为边集 E ( G ) { 0 , 1 , 2 , , | E | 1 } 的双射,则称 为G的一个调和标号。称G为调和图。

由定义2可以看出,若把图的序列标号对边数|E|取摸,就得到了该图的调和标号,即序列标号只是调和标号的特殊情。

定义3:对于自然数 n 3 ,设 P n = x 1 x 2 x n 为n个点的路,在Pn上xi与xi+2之间增加 m i 1 条长为二的路 x i y i , j x i + 2 i = 1 , 2 , , n 2 j = 1 , 2 , , m i ,所得的图称为链路。记作 P n ( m 1 , m 2 , , m n 2 ) 。链路满足

V ( P n ( m 1 , m 2 , , m n 2 ) ) = V ( P n ) { y i , j | 1 i n 2 , 1 j m i } ,

E ( P n ( m 1 , m 2 , , m n 2 ) ) = E ( P n ) { x i y i , j , y i , j x i + 2 | 1 i n 2 , 1 j m i } .

m i = m 1 1 i n 2 ,记 P n ( m 1 , m 2 , , m n 2 ) 为Pn(m)。如图1图2所示。

Figure 1. P7(2)

图1. 图P7(2)

Figure 2. P6(1)

图2. 图P6(1)

Figure 3. P7(2) and k-graceful labelling

图3. 图P7(2)及其k-优美标号

Figure 4. P6(2) and sequential labelling

图4. 图P6(2)及其序列标号

本文给出了图Pn(m)的k-优美标号和序列标号。得到了如下定理。

定理1:对于自然数 n 3 m 1 ,Pn(m)是k-优美图。

定理2:对于自然数 n 4 m 1 ,Pn(m)是序列图。

推论1:( [2] 中定理1)对于自然数 n 3 ,Pn(2)是优美图。

推论2:对于自然数 n 4 m 1 ,Pn(m)是调和图。

文中图3是图P7(2)的k-优美标号,图4是图P6(2)的序列标号

可以进一步讨论图 P n ( m 1 , m 2 , , m n 2 ) 优美性和序列性,我们有:

问提1:对于自然数 n 3 m i 1 1 i n 2 P n ( m 1 , m 2 , , m n 2 ) 是否是k-优美图?

问提2:对于自然数 n 4 m i 1 1 i n 2 P n ( m 1 , m 2 , , m n 2 ) 是否是序列图?

2. 定理的证明

| V ( P n ( m ) ) | = m n 2 m + n | E ( P n ( m ) ) | = 2 m n 4 m + n 1

2.1. 定理1的证明

分两重情况定义Pn(m)的顶点标号f如下:

情况1:n为奇数

f ( x 2 i 1 ) = i 1 , i = 1 , , ( n + 1 ) / 2 ,

f ( x 2 i ) = m n 3 m + n i + k 1 , i = 1 , , ( n 1 ) / 2 ,

f ( y 2 i 1 , j ) = 2 m n 2 m + n ( 2 m 1 ) i 2 j + k 1 , i = 1 , , ( n 1 ) / 2 , j = 1 , , m ,

f ( y 2 i , j ) = n 2 m 2 + ( 2 m 1 ) i + 2 j , i = 1 , , ( n 3 ) / 2 , j = 1 , , m .

下面验证f是Pn(m)的k-优美标号。

1) 不同的顶点其标号不同。

a) 显然有如下结论:

f ( x 2 i 1 ) f ( x 2 j 1 ) ( i j , 1 i , j ( n + 1 ) / 2 ),

f ( x 2 i ) f ( x 2 j ) ( i j , 1 i , j ( n 1 ) / 2 ),

( i = j 时, ; s = t 时, i ≠ j , 1 ≤ s , t ≤ m , 1 ≤ i , j ≤ ( n − 1 ) / 2 ),

f ( y 2 i , s ) f ( y 2 j , t ) ( i = j 时, s t s = t 时, i j , 1 s , t m , 1 i , j ( n 3 ) / 2 ).

b) 设

A 0 = { f ( x 2 i 1 ) | 1 i ( n + 1 ) / 2 } , C 0 = { f ( y 2 i 1 , j ) | 1 i ( n 1 ) / 2 , 1 j m } ,

A 1 = { f ( x 2 i ) | 1 i ( n 1 ) / 2 } , C 1 = { f ( y 2 i , j ) | 1 i ( n 3 ) / 2 , 1 j m } .

A 0 A 1 = A 0 C 0 = A 0 C 1 = A 1 C 0 = A 1 C 1 = C 0 C 1 = .

事实上

min A 0 = f ( x 1 ) = 0 , max A 0 = f ( x n ) = ( n 1 ) / 2 ,

min A 1 = f ( x n 1 ) = m n 3 m + ( n 1 ) / 2 + k , max A 1 = f ( x 2 ) = m n 3 m + n 2 + k ,

min C 0 = f ( y n 2 , m ) = m n 3 m + 3 ( n 1 ) / 2 + k , max C 0 = f ( y 1 , 1 ) = 2 m n 4 m + n 2 + k ,

min C 1 = f ( y 1 , 1 ) = n 1 , max C 1 = f ( y n 3 , m ) = m n 3 m + ( n 1 ) / 2 .

于是有 min A 0 < max A 0 < min C 1 < max C 1 < min A 1 < max A 1 < min C 0 < max C 0

2) max { f ( v ) | v V ( P n ( m ) ) } = max C 0 = 2 m n 4 m + n 2 + k = k + | E ( P n ( m ) ) | 1

3) 不同的边其标号不同。

I 1 = { | f ( y 2 i 1 , j ) f ( x 2 i 1 ) | , | f ( y 2 i 1 , j ) f ( x 2 i + 1 ) | | 1 i ( n 1 ) / 2 , 1 j m } = { 2 m n 4 m + n 2 + k , 2 m n 4 m + n 3 + k , , m n 3 m + n 1 + k } ,

I 2 = { | f ( x 2 i ) f ( x 2 i 1 ) | , | f ( x 2 i ) f ( x 2 i + 1 ) | | 1 i ( n 1 ) / 2 } = { m n 3 m + n 2 + k , m n 3 m + n 3 + k , , m n 3 m + k } ,

I 3 = { | f ( y 2 i , j ) f ( x 2 i ) | , | f ( y 2 i , j ) f ( x 2 i + 2 ) | | 1 i ( n 3 ) / 2 , 1 j m } = { m n 3 m 1 + k , m n 3 m 2 + k , , k } .

由(3)显然有 a , b I i i = 1 , 2 , 3 ,有 a b 。又因

max I 1 = 2 m n 4 m + n 2 + k , min I 1 = m n 3 m + n 1 + k ,

max I 2 = m n 3 m + n 2 + k , min I 2 = m n 3 m + k ,

max I 3 = m n 3 m 1 + k , min I 3 = k .

min I 3 < max I 3 < min I 2 < max I 2 < min I 1 < max I 1 ,进而有, I i I j = i j 1 i , j 3 。于是,有 a b

4) max { f ( e ) | e E ( P n ( m ) ) } = max I 1 = 2 m n 4 m + n 2 + k = k + | E ( P n ( m ) ) | 1

综合(1)~(4),由优美图的定义知,f是Pn(m)的k—优美标号。故得Pn(m)是k-优美图。

情况2:n为偶数

f ( x 2 i 1 ) = i 1 , i = 1 , , n / 2 ,

f ( x 2 i ) = m n 2 m + n i + k 1 , i = 1 , , n / 2 ,

f ( y 2 i 1 , j ) = 2 m n 2 m + n ( 2 m 1 ) i 2 j + k 1 , i = 1 , , ( n 2 ) / 2 , j = 1 , , m ,

f ( y 2 i , j ) = n 2 m 2 + ( 2 m 1 ) i + 2 j , i = 1 , , ( n 2 ) / 2 , j = 1 , , m .

类似于情况1的证明,易验证在情况2中f是Pn(m)的k-优美标号。

定理1证毕。

2.2. 定理2的证明

分两重情况定义Pn(m)的顶点标号如下:

情况1: n 1 ( mod 3 )

情况1.1:n为奇数

θ ( x 2 i 1 ) = ( n 1 ) / 2 + i , i = 1 , , ( n + 1 ) / 2 ,

θ ( x 2 i ) = i 1 , i = 1 , , ( n 1 ) / 2 ,

θ ( y 2 i 1 , j ) = 2 m n 4 m + 3 n 4 3 i 2 j ( n 2 ) , i = 1 , , ( n 1 ) / 2 , j = 1 , , m ,

θ ( y 2 i , j ) = 2 m n 4 m + 5 ( n 1 ) / 2 3 i 2 j ( n 2 ) , i = 1 , , ( n 3 ) / 2 , j = 1 , , m .

下面验证θ是Pn(m)的序列标号。

1) 不同的顶点其标号不同。

a) 设

B = { θ ( x 2 i ) | 1 i ( n 1 ) / 2 } { θ ( x 2 i 1 ) | 1 i ( n + 1 ) / 2 } ,

C j = { θ ( y 2 i 1 , j ) | 1 i ( n 1 ) / 2 } , j = 1 , , m ,

D j = { θ ( y 2 i , j ) | 1 i ( n 3 ) / 2 } , j = 1 , , m .

由θ的定义有

min B = 0 , max B = n ,

min C j = 2 m n 4 m + ( 3 n 5 ) / 2 2 j ( n 2 ) , j = 1 , , m ,

max C j = 2 m n 4 m + 3 n 7 2 j ( n 2 ) , j = 1 , , m ,

min D j = 2 m n 4 m + n + 2 , j = 1 , , m ,

max D j = 2 m n 4 m + 5 ( n 1 ) / 2 3 2 j ( n 2 ) , j = 1 , , m ,

min B < max B < min D m < max D m < min C m < max C m < min D m 1 < max D m 1 < < min D 1 < max D 1 < min C 1 < max C 1 。于是有 B C j = B D j = C j D j = j = 1 , , m 。得 u , v V ( P n ( m ) ) ,若 u v ,有 θ ( u ) θ ( v )

2) max { θ ( v ) | v V ( P n ( m ) ) } = 2 m n 4 m + n 3 < 2 m n 4 m + n 1 = | E ( P n ( m ) ) |

3) 不同的边其标号不同。

J 0 = { θ ( x i ) + θ ( x i + 1 ) | 1 i n 1 } = { ( n + 1 ) / 2 , ( n + 1 ) / 2 + 1 , , ( n + 1 ) / 2 + n 2 } ,

J 1 , j = { θ ( y 2 i 1 , j ) + θ ( x 2 i + 1 ) , θ ( y 2 i 1 , j ) + θ ( x 2 i 1 ) | 1 i ( n 1 ) / 2 } = { 2 m n 4 m + ( 7 n 11 ) / 2 2 j ( n 2 ) , 2 m n 4 m + ( 7 n 11 ) / 2 1 2 j ( n 2 ) , , 2 m n 4 m + ( 5 n 7 ) / 2 2 j ( n 2 ) } , j = 1 , , m ,

J 2 , j = { θ ( y 2 i , j ) + θ ( x 2 i + 2 ) , θ ( y 2 i , j ) + θ ( x 2 i ) | 1 i ( n 3 ) / 2 } = { 2 m n 4 m + ( 5 n 9 ) / 2 2 j ( n 2 ) , , 2 m n 4 m + ( 3 n 1 ) / 2 2 j ( n 2 ) } , j = 1 , , m ,

J 1 = J 2 , m J 1 , m = { ( 3 n 1 ) / 2 , ( 3 n 1 ) / 2 + 1 , , ( 5 n 9 ) / 2 } { ( 5 n 7 ) / 2 , ( 5 n 7 ) / 2 + 1 , , ( 7 n 11 ) / 2 } ,

J 2 = J 2 , m 1 J 1 , m 1 = { ( 7 n 9 ) / 2 , ( 7 n 9 ) / 2 + 1 , , ( 9 n 17 ) / 2 } { ( 9 n 15 ) / 2 , ( 9 n 15 ) / 2 + 1 , , ( 11 n 19 ) / 2 } ,

J m = J 2 , 1 J 1 , 1 = { 2 m n 4 m ( n 7 ) / 2 , 2 m n 4 m ( n 7 ) / 2 + 1 , , 2 m n 4 m + ( n 1 ) / 2 } { 2 m n 4 m + ( n + 1 ) / 2 , 2 m n 4 m + ( n + 1 ) / 2 + 1 , , 2 m n 4 m + 3 ( n 1 ) / 2 }

于是有 J i J j = i j 0 i , j m ,故得 e , f E ( P n ( m ) ) ,若 e f ,有 θ ( e ) θ ( f )

4) J = J 0 J 1 J 2 J m = { ( n + 1 ) / 2 , ( n + 1 ) / 2 + 1 , , 2 m n 4 m + 3 ( n 1 ) / 2 } = { ( n + 1 ) / 2 , ( n + 1 ) / 2 + 1 , , ( n + 1 ) / 2 + | E ( P n ( m ) ) | }

综合(1)~(4),由序列图的定义知,θ是Pn(m)的序列标号。故得Pn(m)是序列图。

情况1.2:n为偶数

θ ( x 2 i 1 ) = n / 2 + i , i = 1 , , n / 2 ,

θ ( x 2 i ) = i 1 , i = 1 , , n / 2 ,

θ ( y 2 i 1 , j ) = 2 m n 4 m + 3 n 4 3 i 2 j ( n 2 ) , i = 1 , , ( n 2 ) / 2 , j = 1 , , m ,

θ ( y 2 i , j ) = 2 m n 4 m + ( 5 n 2 ) / 2 3 i 2 j ( n 2 ) , i = 1 , , ( n 2 ) / 2 , j = 1 , , m .

类似于情况1.1的证明,易验证在情况1.2中θ是Pn(m)的序列标号。

在情况2中,可与情况1同理验证θ是Pn(m)的序列标号。故只给出下列标号,不加验证。

情况2: n 0 , 2 ( mod 3 )

情况2.1:n为奇数

θ ( x 2 i 1 ) = ( n 3 ) / 2 + i , i = 1 , , ( n + 1 ) / 2 ,

θ ( x 2 i ) = i 1 , i = 1 , , ( n 1 ) / 2 ,

θ ( y 2 i 1 , j ) = 2 m n 4 m + 3 n 4 3 i 2 j ( n 2 ) , i = 1 , , ( n 1 ) / 2 , j = 1 , , m ,

θ ( y 2 i , j ) = 2 m n 4 m + ( 5 n 7 ) / 2 3 i 2 j ( n 2 ) , i = 1 , , ( n 3 ) / 2 , j = 1 , , m .

情况2.2:n为偶数

θ ( x 2 i 1 ) = ( n 2 ) / 2 + i , i = 1 , , n / 2 ,

θ ( x 2 i ) = i 1 , i = 1 , , n / 2 ,

θ ( y 2 i 1 , j ) = 2 m n 4 m + 3 n 4 3 i 2 j ( n 2 ) , i = 1 , , ( n 2 ) / 2 , j = 1 , , m ,

θ ( y 2 i , j ) = 2 m n 4 m + ( 5 n 4 ) / 2 3 i 2 j ( n 2 ) , i = 1 , , ( n 2 ) / 2 , j = 1 , , m .

定理2证毕。

文章引用:
刘春峰. 链路Pn(m)优美性和序列性[J]. 理论数学, 2018, 8(6): 723-729. https://doi.org/10.12677/PM.2018.86097

参考文献

[1] 马克杰. 优美图[M]. 北京: 北京大学出版社, 1991.
[2] 路线, 李秀芬. 关于链路Pn2*的优美性[J]. 上侥师专学报, 1994, 6(14): 26-30.