完全二部图优美性质探索

发布时间：2019-08-26 11:45

【摘要】：图论的二部图及其标号在实际应用中较多,尤其最近图标号被应用于新型的图形密码设计.首先构造出了组合完全二部图与串联完全二部图,发现了一种叫做奇边魔幻全标号的标号,并给出了组合完全二部图具有奇边魔幻全标号的证明.此外,得出了串联完全二部图是优美图、(k,d)-优美图的结论.
【图文】：

示意图,完全二部图

Ｇ为（ｋ，ｄ）－优美图．定义３对于给定的（ｐ，ｑ）－图Ｇ，如果存在一个映射ｆ：Ｖ（Ｇ）→［０，２ｑ－１］，使得图Ｇ中任意两个顶点ｘ、ｙ满足ｆ（ｘ）≠ｆ（ｙ）且定义边ｕｖ∈Ｅ（Ｇ）的标号为ｆ（ｕｖ）＝ｆ（ｕ）＋ｆ（ｖ）．当｛ｆ（ｕｖ）：ｕｖ∈Ｅ（Ｇ）｝＝［１，２ｑ－１］ｏ时，则称ｆ为图Ｇ的一个奇边魔幻全标号，图Ｇ为奇边魔幻图．图１是组合完全二部图的示意图，它由支架与完全二部图组成，而支架是由顶点ａ１，ａ２，…，ａｓ依次连接，完全二部图则是由图Ｇｉ（ｉ∈［１，ｓ］）构成，Ｇｉ即为Ｋｍ，ｎ．其中Ｖ（Ｇｉ）＝｛ａｉ，ｂｉ，ｔ，ｃｉ，ｋ｜ｔ∈［１，ｍ］，ｋ∈［１，ｎ］，ｉ∈［１，ｓ］｝，Ｅ（Ｇｉ）＝｛ａｉｂｉ，１，ｂｉ，ｔｃｉ，ｋ，ａｉａｉ＋１｜ｔ∈［１，ｍ］，ｋ∈［１，ｎ］，ｉ∈［１，ｓ］｝，再将每个完全二部图Ｇｉ中的ａｉ（ｉ∈［１，ｓ］）相连．图１一个组合完全二部图Ｆｉｇ．１Ａｃｏｍｂｉｎａｔｏｒｉｃｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈｓ图２是串联完全二部图示意图，它由ｎ个完全二部图依次连接而成，完全二部图则是由图Ｇｉ构成，Ｇｉ即为Ｋｍｉ，ｎｉ，其中Ｖ（Ｇｉ）＝｛ｂｉ，ｔｉ，ｃｉ

示意图,完全二部图

ｂｉ，ｔ，ｃｉ，，ｋ｜ｔ∈［１，ｍ］，ｋ∈［１，ｎ］，ｉ∈［１，ｓ］｝，Ｅ（Ｇｉ）＝｛ａｉｂｉ，１，ｂｉ，ｔｃｉ，ｋ，ａｉａｉ＋１｜ｔ∈［１，ｍ］，ｋ∈［１，ｎ］，ｉ∈［１，ｓ］｝，再将每个完全二部图Ｇｉ中的ａｉ（ｉ∈［１，ｓ］）相连．图１一个组合完全二部图Ｆｉｇ．１Ａｃｏｍｂｉｎａｔｏｒｉｃｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈｓ图２是串联完全二部图示意图，它由ｎ个完全二部图依次连接而成，完全二部图则是由图Ｇｉ构成，Ｇｉ即为Ｋｍｉ，ｎｉ，其中Ｖ（Ｇｉ）＝｛ｂｉ，ｔｉ，ｃｉ，ｋｉ｜ｉ∈［１，ｓ］，ｔｉ∈［１，ｍｉ］，ｋｉ∈［１，ｎｉ］｝，Ｅ（Ｇｉ）＝｛ｂｉ，ｔｉｃｉ，ｋｉ，ｂｉ，１ｃｉ－１，ｎ｜ｉ∈［１，ｓ］，ｔｉ∈［１，ｍｉ］，ｋｉ∈［１，ｎｉ］｝．图２一个串联完全二部图Ｆｉｇ．２Ａｓｅｒｉｅｓｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈｓ２主要结论定理１组合完全二部图具有奇边魔幻标号．证明设图Ｇ是组合完全二部图，定义图Ｇ的一个标号ｆ：令ｆ（ｂ１，１）＝０．对ｉ∈［１，ｓ］，ｔ∈［１，ｍ］，ｋ∈［１，ｎ］分情形证明．若ｍ＝３，ｎ＝４．当ｓ＝１时，有ｆ（ｂ１，２）＝８，ｆ（ｂ１
【作者单位】：西北师范大学数学与统计学院;
【基金】：国家自然科学基金资助项目(61163037,61163054,61363060)
【分类号】：O157.5

【相似文献】