关于四角仙人掌图的优美性.pdfVIP

第 14 卷 哈尔滨师范大学自然科学学报 　　　　　　　Vol 14 ,No3 1998 第 3 期 NA TURAL SCIENCES J OURNAL OF HARB IN NORMAL UN IV ERSIT Y 　　　 关于四角仙人掌图的优美性 路　线　李秀芬 ( 吉林职业师范学院) 　　【摘要】　本文讨论了四角仙人掌图的优美性 ,给出了几类四角仙人 掌图是优美图的一些结果 ,从而部分回答了 A Rosa 在 [ 1 ] 中提出的猜 想 　　 关键词 : 优美图 ; 四角仙人掌图;交错二分图 ( 1988 年 ,ARosa 曾在[1 ]之中给出了三角、四角、五角仙人掌图 即所有的块皆为三角 ) 形、四边形、五边形的连通图 等概念 ,并提出一些猜想 如“所有四角仙人掌图都是优美 图”就是其中之一 ,至今为止 ,这一猜想也未被证明或否 ,得到的结果也甚少[ 2 ] 本文获得 了部分结果 定义 1[3 ] 　对于一个简单图 G ( V , E) ,如果对每一个顶点 v ∈V ,存在一个非负整数 L ( ) ( ) v 顶点 v 的标号 满足 : ( ) ( ( ) 1 u , v ∈V ,若 u ≠v ,则 l u ≠l v ; (2) max{ l ( v ) | v ∈V } = | E | ; ( ) ( ) ( ) ( ) ( ) ( ) 3 e ′, e ″∈E ,若 e ′≠e ″,则 l ′e ′≠l ′e ″ 这里定义 l ′e = | l u - l v | ,其中 uv = e 那么称图 G 是优美图, l ( v ) 称图 G 的优美标号 定义 2 [4 ] 　设 θ( v ) 是二分图 G = ( X , Y ; E) 一个优美标号, 且满足 : u ∈X , v ∈Y 都有 θ( u) θ( v) 则称 θ( v) 是 G 的一个交错标号 若 G 有一个交错标号, 则 G 是交错二分图 定义 3 　由 m 个四边形块构成的, 恰有一个公共顶点的连通图化作 D m , 4 ; 由 m 个四边 形串联起来, 构成割点图为一条通路, 并且相领的两个割点之间不是同一四边形的相邻顶 点, 这样得到四角仙人掌图称为长度为 m 的四角仙人掌图的一个简单通路记作 Pm , 4 Pm , 4 ( ) 之中与割点不相邻的顶点称路 Pm , 4 的端点 有两个 由 n 个长度为 m 的四角仙人掌图的 简单通路 Pm , 4 构成的, 并且将这 n 个 Pm , 4 的一个端点粘接在一起成为一个顶点而得到的图 称等长幅射四角仙人掌图, 记作 Gn , m 如图 1 所示, 图中2 n 度顶点称为三原点 从三原点 开始长度如 m 的四角仙人掌图的简单通路是 Gn , m 的一个辐轴 收稿日期 :1998 - 2 - 01 24 哈尔滨师范大学自然科学学报 1998 年 图 1 　Gn , m 　　定理 1 　对于任意自然数 m , n ,等长幅射四角仙人掌图 Gn , m 是优美图 证明 　设等长幅射四角仙人掌图 Gn , m 三原点为 x 0