图(p≤9)的边幻和全标号

图的边幻和全标号是指图中任意边及其两个顶点的标号和为常数,且标号取值一一对应于从1至点边之和的自然数集合.设计了一种递归算法,采用了与目标函数相结合的算法优化策略,实现了对9个点内所有简单连通图的边幻和性判定.结果表明,当p≤9时,所有的树图、单圈图和双圈图都是边幻和全标号图;当点边数值满足一定条件时,发现若干图类是边幻和全标号图或非边幻和全标号图,结合已有结果,猜测当点数超过9时,相关结论也成立.其中,已经证明点数不超过12时的猜测成立.

单圈图的边幻和全标号

对于图G(p,q),若存在一个映射f:V(G)∪E(G)→{1,2,…,p+q},使得任意边uv∈E(G),满足f(u)+f(v)+f(uv)=K,K为常数,则图G(p,q)为边幻和图。设计了一种算法对16个点以内的单圈图进行标号,依据得到的结果,找到了两类特殊单圈图的标号规律,定义Cn▽Sm和CnΔSm来刻画此两类特殊单圈图,并给出其相关定理及证明。结果表明,点数小于等于16的所有单圈图均具有边幻和全标号,且其中绝大部分是超级边幻和全标号,从而猜测点数多于16的单圈图也具有边幻和全标号。

两类联图的边幻和全标号

设计了一种递归算法,得到了15个点内扇图与单圈图组成的联图的边幻和全标号通过结果分析,发现两类联图F_(n)↑C_(l)↑S_(m)和F_(n)↑C_(l)↓S_(m)均为EMTL图.进而总结若干定理并给出证明结合已有结果,猜想所有的联图皆为EMTL图.

非边幻和图的若干定理及证明

若G(p,q)的点边标号一一映射到{1,2,…,p+q},使得任意边与其关联顶点的标号值之和为一个常数,这种标号被称之为边幻和全标号。本文设计了一种算法得到了9个点以内所有简单无向连通图中的非边幻和图,发现其中一些图具有某种相同的特征,因此定义了新的图运算符Kn▷Cm和KnΔSm来刻画这两类联图,通过引入西顿序列,证明了在特定条件下,两类联图为非边幻和图。