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