论文摘要
图的标号问题是图论中一个比较新的课题,它可追溯到1950年信号带宽的优化问题:源于主要的非零数字信号通常位于一个比较窄的带宽中。1966年Rosa给出了图标号的一个新的概念——图的优美标号（Graceful Labeling）,并提出了著名的所有的树都是优美的猜想。图的标号是指在一定规则条件下对图的顶点与边进行标号。一个图的顶点标号是图的顶点集到整数集的映射,而边标号则是图的边集到整数集的映射,根据对映射的不同要求,产生了各种类型的图的标号,例如优美标号、超幻和标号、调和标号和亲切素标号等等。图的亲切素标号是由Sumndarm,Ponrai和Somasundram于2005年提出来的。如果一个带有顶点集V的图存在一个从V到{1,2,…|V|}双射f,对每条最大公约数gcd（f（u）,f（v））=1的边标号为1,并且对最大公约数gcd（f（u）,f（v））＞1的边标号为o,则标号为1的边的数量和标号为0的边的数量相差最多为1,这类图被称作有亲切素标号。Gn是一个简单的非平凡的连通的三正则图,点集V（Gn）={ai,bi,ci,di:0≤i≤n-1),边集E（Gn）={aiai+1,bibi+1,cici+1,diai,dibi,dici:0≤i≤n-1),点的标号对n取模,Hn可以由Gn通过用边bn-1c0,cn-1b0替换bn-1b0,cn-1c0得到。如果n为奇数且n≥5,Hn被称作Flower Snark图。其他的图,被称作Flower Snark图的相关图。Sumndarm等证明了如下几类图是可亲切素标号的:循环图Cn（n≥6）、路径Pn（n≠3,5）、星图K1,n（n为奇数）、双星图（Bistars graph）、龙图（Dragon graph）、皇冠图（Crown graph）、三角蛇图Tn（n≥3）以及梯子图（Ladder graph）.本文设计了计算机辅助下求解的Kn（o|¨）del图和Flower Snark及其相关图的亲切素标号,并用数学的方法给予了证明。