三角拼图的超边幻和标号.pdf

汕头大学学报 (自然科学版) 第27卷 第2期 JournalofShantouUniversity(NaturalScience) V01．27 NO．2 文章编号：1001—4217(2012)02—0005—05 三角拼图的超边幻和标号 刘家保 ．王 林 (安徽新华学院，安徽 合肥 230088) 摘 要：幻类标号是由数论中幻方的概念而提出的一类图标号，图标号问题已引起广泛的关 注与研究．本文主要研究j三角拼图的超边幻和标号问题 ，给出其超边幻和标号的算法和严格 的数学证明． 关键词：超边幻和标号 ；超边幻和图；图类 中图分类号：O157．5 文献标识码：A O 引 言 图标号问题是图论中的一类重要研究课题 ．起始于上世纪六十年代A·Rosa的著名 优美树猜想．其背景来源于众多实际问题。应用范围已深入到诸如编码理论 、计算机 、 交换网络、 一射线、天文学 、雷达等领域．超边幻和标号问题是一类对图的标号问题． 具有超边幻和标号的图被称为超边幻和图． 超边幻和图是图论中极其有趣的内容．目前国内外 已经取得 了很多与超边幻和标号 相关的重要成果[I_Ol，主要是集中在非连通图、树、完全图及其相关图和回路及其相关 图等方面的研究成果．Enomoto等人猜想：每棵树都是超边幻和图．本文对三角拼图的 超边幻和标号问题作了全面探索和研究，我们给出了相应的超边幻和标号算法，且验证 三角蛇图是其一个特例 7【]．并给出了严格的数学证明．从而得出三角拼图是超边幻和图 等结论． 1 基本概念 定义 1 对于一个给定的简单图G=(V，E)．存在一个双射函数L： (G)UE(G)一 {1，2，…，l(G)UE(C)I}，使得对所有的边xy∈E(G)，，Y∈v(G)，都有L(x)+L(y)+ L(xy)=C，C为常数，则称 ，J为图G的边幻和标号(edge—magictotallabeling)，图G称 为具有边幻和标号 ，J的边幻和图(edge—magictotalgraph) ． 收稿 日期：2011—01—06 作者简介：刘家保(1982一)，男，汉，安徽穴安人，讲师，硕：j二．研究方向：图论与组合网络 基金项 目：安徽省高等学校省级 自然科学基金项 目(No：KJ2010B076) 6 汕头大学学报 (自然科学版) 第27卷 定义2设L为图G(v，E)的边幻和标号，如果顶点标号满足：((G))={l，2，…，(G)1， 则称 为图G的超边幻和标号(superedge—magictotallabeling) 图G称为具有超边幻和 ， 标号L的超边幻和图(superedge—magictotalgraph)t1． 定义 3 设D(s)表示具有 s个顶点且满足以下条件的图类 ： (1)∈N ，S三O(mod2)且s≥4： (2)顶点集为V(D(s))= ，z，…．}； (3)边集为E(D(s))：{溉+li=1，3，…，s一3)u{+。li=1，3，…，s—l}u {xix+li：2，4，…，s一2}U{x+I=1，3，…，s一31． 则图D(s)称为三角拼图，其结构如图1所示．超边幻和标号如图2所示． ＼＼＼ ＼＼ ＼ 2 4 6 2n 2n+2 X6 +2 三角拼图D(s1 图2三角拼 图O(sl的超边幻和标号 2 主要结论 由于在网格(grid)-~G(D(s))= +．Xi+2+