梯子是下整和图.pdfVIP

第 23卷第 6期 滨州学院学报 2007年 12月 V01．23，NO．6 Jour~al of Binzhou University Dec．，2007 梯子是下整和图 高秀莲 (德州学院 数学系，山东 德州 253023) 摘 要：下整和标号与排斥下整和标号是图的新的压缩表示．一个图G称为下整和图，若它同构 于某个 S(二二Q 的下整和图．图L ×K z称为梯子．现证明了梯子是下整和图． 关键词：梯子；下整和数；下整和标号；下整和图 中图分类号：O 1 57．5 文献标识码：A 文章编号：1 673 2618(2007)06—0061—03 文中所用图论基本术语与符号遵循文献[1]．1990年Harary一?提出和图的概念，1994年Harary一 提 出整和图的概念．令N(z)表示正整数(整数)集，N(z)的非空有限子集S的和(整和)图G-(S)是图(S， E)，其中E当且仅当“+ ∈s．一个图G称为和(整和)图，若它同构于某个s(二二N(z)的和(整和)图．即 s给出了G的一个和(整和)标号，并且将顶点与其标号不加区分．G的和数(整和数)口(G)( (G))是使得G U nK 是和图(整和图)的非负整数”的最小值．2003年Miller 等提出了排斥图的概念．图G U nK 的 (整)和标号S称为排斥的(exclusive)，若对每条边E(G)，“+ ∈S＼ (G)．如果G U nK 的任意边的两 端点(标号)之和都是孤立点，则G称为排斥图；图G的排斥(整)和数￡(G)( (G))是使得G U nK 有排 斥(整)和标号的非负整数”的最小值．显然对任意的图G有 (G)≤口(G)≤￡(G)； (G)≤ (G)≤￡(G)． 从实用的观点来看，各种和图标号都可用作图的压缩表示，即表示图的数据结构．当利用输入图的压 缩表示来工作时，数据压缩不仅可以节省内存，还可以加快某些图算法的运算速度．近年来和图理论发展 很快，可参见文献[5—7]． 2004年李敏 提出下整和图的概念．用L _j表示不超过实数 的最大整数(称为 的下整数)，Q_表 示正有理数集．Q。。的非空有限子集s的下整和图G一(S)是图(S，E)，其中“ ∈E当且仅当L“+ _I∈ S．一个图G称为下整和图，若它同构于某个S(二二Q一的下整和图．因此说S给出G的一个下整和标号，并且 顶点与标号不加区分．下整和数 (G)是使得G U nK 是下整和图的非负整数”的最小值．下整和标号是 图的新的压缩表示． 定义 ×K：称为弟子，记为L 定理 梯子是下整和图． 证明 设A一 {“ ，“2，…，“，，}，B一 {b ，b2，…，b， }，S— (L )一A U B， E(L )= {ala ，bib ，akb f 1≤ i， ≤ ”一1，1≤ ≤ ，1≤ k≤ ”}． 给出L 的一组标号 收稿日期：2006—11—06 基金项目：山东省教育科学十一五规划资助项目(1153Z196) 作者简介：高秀莲(1 969一)，女，山东夏津人，讲师，硕士，主要从事图论研究 62 滨州学院学报 第 23卷 下面验证所给标号为L， 的一个下整和标号． (1)显然 S中元素互异． (2)验证任意边和下整数属于S： L“ +＆ _』：L~l--ai 1+ +3×10 —L”十1—3×(10一 一10 ) ”( 1的奇数)， L“ 十 —L“ +”一“ 一”( 1的偶数)， L“ +“ —L”十9——9 4-3×10一 2 —L 77+3×10 I ， I ==： ， 6，4-6 rj—L b 4-” b 一”( 为奇数)， L 6 +6川j—L b ～ 4-b —