优雅图猜想

赵 科， 李 敬 文， 魏 众 德

( 兰州交通大学 电子与信息工程学院， 甘肃 兰州 730070 )

0 引 言

国内外学者主要在研究特殊图的优雅性，例如圈、路、扇图等目前已经证明是优雅的．Rosa提出非优美图产生的3个原因[8]：(1)图G的顶点过多而边数太少；(2)图G边数过多而顶点太少；(3)图G的边数具有错误的奇偶性．以上条件同样适用于优雅标号．本文根据文献[9]中生成非同构图的算法，得到9个点之内的所有连通图，结合设计的优雅标号算法，得到所有优雅图和非优雅图的数量．

1 定义及基本概念

定义1[1]对于任意的简单连通图G=(V，E)，如果对每一个顶点v∈V，都对应一个非负整数f(v)(f(v)为顶点v的标号)，且满足

(1)∀v1，v2∈V，如果v1≠v2，则f(v1)≠f(v2)；

(2){f(v)|v∈V}∈{0，1，2，…，|E|}；

(3)∀e1，e2∈E，如果e1≠e2，则g(e1)≠g(e2)，其中g(e)=(f(v1)+f(v2))mod (q+1)，e=v1v2；

(4){g(e)|e∈E}∈{1，2，…，|E|}

则称f为图G的一个优雅标号，图G称为优雅图．

定义2对于边数为q的优雅图，满足以下条件：

(1)min(f(u)，f(v))≥0；

(2)max(f(u)，f(v))≤|E|；

(3)(f(u)+f(v))mod (q+1)=g(e)，且g(e)≠0

则称为边数为q的优雅集合，又称q优雅空间．如表1所示，对于每个g(e)，只取一个二元组(m，n)，这些二元组集合组成的图都是优雅的．

m的取值范围为{0，1，…，q}；n的取值范围可通过如下公式：n=g(e)-m≥0？g(e)-m：g(e)-m+q+1判断取得．

在优雅空间中，当m=n时，因每个点的标号不同，故去除；为了避免重复，当m>n时，去除该二元组(m，n)．具体如表1所示．

表2为(5，10)图的优雅空间，其中粗体的二元组为它的一种优雅标号，如图1所示．

表1 q优雅空间

表2 q=10优雅空间

图1 (5，10)图优雅标号

猜想1[1]所有的树都是优雅的．

2 解决思路及算法

2.1 解决思路

本文所研究的图均为简单连通图，具有p个顶点和q条边的图称为(p，q)图，其中q的范围为p-1≤q≤p(p-1)/2．当p-1>q时，该图为非连通图，不在本文研究范围之内．判断任意一个连通图是否为优雅图的解决思路如下：