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

Algorithm for Adjacent Vertex Reducible Edge Labeling of Some Special Graphs and Their Associated Graphs

作　　者：李敬文[1] 兰琳钰 张树成 罗榕 LI Jingwen;LAN Linyu;ZHANG Shucheng;LUO Rong(School of Electronics and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,Gansu,China)

机构地区：[1]兰州交通大学电子与信息工程学院,甘肃兰州730070

出　　处：《武汉大学学报（理学版）》2022年第5期463-470,共8页Journal of Wuhan University:Natural Science Edition

基　　金：国家自然科学基金(11961041;62062049);甘肃省媒体融合技术与传播重点实验室开放课题(21ZD8RA008)

摘　　要：设G(V,E)是一个简单图,若存在一一映射f:E(G)→{1,2,…,|E|},使得对任意两点uv∈E(G),如果d(u)=d(v),有S(u)=S(v),其中S(u)=∑uω∈E(G)∫(uω),d(u)表示点u的度,则称f为G的邻点可约边标号(adjacent vertex reducible edge labeling,AVREL)。在已有图标号概念与可约染色概念的基础之上,结合实际问题提出了邻点可约边标号新概念,并设计了一种新的邻点可约边标号算法(简称AVREL算法)。该算法对边初始标号,然后针对邻点可约边标号的解空间进行递归搜索,最终筛选出满足边标号的图集并以标号矩阵的形式输出。经过对算法结果分析,总结出若干路图、扇图、星图、轮图、树图等特殊图及其联图在不同情况下的邻点可约边标号定理,并给出了证明。Let G(V,E)be a simple graph,if there is a one-to-one mapping f:E(G)→{1,2,…,|E|},so that for any two points,if d(u)=d(v),there is S(u)=S(v),where S(u)=∑uω∈E(G)∫(uω),d(u)represents the degree of the point u,then f is the Adjacent Vertex Reducible Edge Labeling(AVREL).Based on the existing graph labeling concept and the reducible concept,this paper proposes a new concept of Adjacent Vertex Reducible Edge labeling combined with practical problems,and designs a new type of Adjacent Vertex Reducible Edge Labeling algorithm(referred to as AVREL algorithm).The algorithm uses the initial label of the edge,and then searches the solution space of the label of the atlas,and finally filters out the atlas that meets the label of the edge and outputs it in the form of a label matrix.After analyzing the results of the algorithm,we summarize several special graphs such as fan graphs,star graphs,wheel graphs,and their associated graphs under different conditions,and gave proofs for the adjacent vertex reducible edge labeling theorems.

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

分 类 号：O157.5[理学—数学]