单圈图的边幻和全标号

发布时间：2024-05-08 20:29

　　对于图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个点以内的单圈图进行标号,依据得到的结果,找到了两类特殊单圈图的标号规律,定义C_n?S_m和C_nΔS_m来刻画此两类特殊单圈图,并给出其相关定理及证明。结果表明,点数小于等于16的所有单圈图均具有边幻和全标号,且其中绝大部分是超级边幻和全标号,从而猜测点数多于16的单圈图也具有边幻和全标号。

【文章页数】：9 页

【部分图文】：

图1Cn?Sm和CnΔSm图

定义3CnΔSm:设Cn的顶点集为{u1,u2,…,un},Sm的顶点集为{v1,v2,…,vm}。CnΔSm表示将Sm的中心节点v1粘接到Cn的一个顶点u1之后得到的图,记为CnΔSm,V(CnΔSm)=V(Cn)∪V(Sm)＼v1,即|V(CnΔSm)|=|V(Cn)|+....

图2图集G(6,12)中EMTL图和NEMTL图

表2中加黑加粗的三元组为图2(1)的解。图2(2)在φ(6,12,K)没有搜到解,故其是NEMTL图。3EMTL算法运行环境、结论及证明

图3单圈图EMTL和SEMTL示例

(4)EMTL和SEMTL示例如图3所示。(5)猜测:对于单圈图G(p,q),当p≥17时存在EMTL。

图4C3?Sm和C4?Sm

|V(G)|=|E(G)|=m+3。C3?Sm顶点标号为:

本文编号：3967783