一类二部图的魔幻标号.pdfVIP

第１７卷 第１期　　　　　　　　　　　　　　兰州石化职业技术学院学报　　　　　　　　　　　　 　　　Ｖｏｌ１７Ｎｏ１ ２０１７年３月 ＪｏｕｒｎａｌｏｆＬａｎｚｈｏｕＰｅｔｒｏｃｈｅｍｉｃａｌＣｏｌｌｅｇｅｏｆＴｅｃｈｎｏｌｏｇｙ Ｍａｒ．，２０１７ 　　文章编号：１６７１－４０６７（２０１７）０１－００４１－０４ 一类二部图的魔幻标号 赵振学，姚　明 （兰州石化职业技术学院信息处理与控制工程系，甘肃 兰州７３００６０） 摘要：为研究需要定义了图的魔幻全空间与向量空间。并采用新方法使魔幻标号可算法 化，给出一类二部图标号的某些结果，以及大规模快速地构造一类二部图的方法。 关键词：ｋ－魔幻全标号；魔幻全标号；对偶标号；全魔幻空间；向量空间；奇优美标号 中图分类号：Ｏ１５７．５ 文献标识码：Ａ ∪Ｅ（Ｇ） ［１，ｐ＋ｑ］｝，若对于图Ｇ的一个全标号函 → 数ｆ，令Ｎ为全体整数集合，对任意的ｓ，ｔ Ｎ，都有 １　 引言及概念 ∈ ｆ （ｕ）＋ｆ（ｓ，ｔ），ｉ（ｖ）＝ｓ＋ｔｆ （ｕｖ）（ｉ ［１， （ｓ，ｔ），ｉ （ｓ，ｔ），ｉ ∈ 综合文献［１］中Ｇａｌｌｉａｎ介绍Ｒｏｓａ猜想：所有 ｍ］）；则说集合Ｐ（Ｇ）为Ｇ的全魔幻集；此外，如果 的树都是优美树，如果Ｒｏｓａ猜想被证明，则Ｒｉｎｇｅｌ 有 Ｖ（Ｇ）＝Ｖ Ｖ，使得Ｖ Ｖ ＝，且Ｖ与Ｖ １ ∪ ２ １∩ ２ １ ２ －Ｋｏｔｚｉｇ猜想成立。然而每一棵树都是优美树的证 均为独立集，则说Ｇ是二部图，记为 。设二部图 Ω Ω 明又成为世界性的难题。优美标号在生物 ＤＮＡ编 有一个ｍ维向量的非空集合 （Ｇ），若集合 （Ｇ）对 Γ Γ 码、网络设计中的寻址、最佳电路、最佳油路的布局 于加法及数乘两种运算封闭，则称集合 （Ｇ）为 Ｇ Γ 和物流等应用领域发挥着重要作用，是图标号研究 的向量空间。此外，对固定的ｔ Ｎ，ｔ ０，称 （Ｇ， ∈ ≠ Γ ［２，３］ ［７］ 的重要课题 。１９７０年，Ｋｏｔｚｉｇ和 Ｒｏｓａ定义了图 ｔ） （Ｇ）为Ｇ的向量子空间 。让Ｎ（ｕ）是一个所 Γ 的边魔幻全标号并提出了魔幻树问题：是否每一棵 有与顶点ｕ邻接的顶点集，度为１的顶点称为叶子。 °