若干特殊图及其联图的邻点可约边标号算法

摘要：

设G(V,E)是一个简单图,若存在一一映射f:E(G)→{1,2,…,丨E丨},使得对任意两点uv∈E(G),如果d(u)=d(v),有S(u)=S(v),其中S(u)=uw∈E(G)∑ f(uw),d(u)表示点u的度,则称f为G的邻点可约边标号(adjacent vertex reducible edge labeling,AVREL).在已有图标号概念与可约染色概念的基础之上,结合实际问题提出了邻点可约边标号新概念,并设计了一种新的邻点可约边标号算法(简称AVREL算法).该算法对边初始标号,然后针对邻点可约边标号的解空间进行递归搜索,最终筛选出满足边标号的图集并以标号矩阵的形式输出.经过对算法结果分析,总结出若干路图、扇图、星图、轮图、树图等特殊图及其联图在不同情况下的邻点可约边标号定理,并给出了证明.

关键词：特殊图、联图、邻点可约边标号、标号算法

所属期刊栏目：68

分类号：O157.6(代数、数论、组合理论)

资助基金：国家自然科学基金;国家自然科学基金;甘肃省媒体融合技术与传播重点实验室开放课题

在线出版日期：2022-11-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：463-470