论文部分内容阅读
关于图的k-优美标号的研究是图论中活跃的研究问题，设图G=(V，E)是简单图，k为非负整数，若存在一个一一映射(公式略)使得导出的一一映射f-∶E→{k+1，k+2，…，k+|E|}，其中对任意的uv∈E，f-(uv)=|f(u)-f(v)|，则称f为G的k-优美标号。如果图G存在一个k-优美标号，则称G为k-优美图，0-优美图简称为优美图。如果对任意的非负整数k，图G均为k-优美图，则称G为强k-优美图(或任意优美图)。
1994年，张树生提出的所有优美偶图是否都是平衡图问题，此问题至今尚未得到完全解决。
本文首先概述了k-优美图的研究现状、应用及其研究意义，然后给出了图论的基础知识，最后研究了特殊并图的k-优美性和平衡性问题，主要包括：
⑴给出当p≥2，q≥3时，图Sn∪Kp,q的优美标号。
⑵给出图Sn∪K2.2(n为正整数)不是平衡图的结论。
⑶证明了当n≠2时，图Sn∪K2,2不是优美图。
⑷给出图S2∪K2,2’S2UK3,2和C6∪P3的强k-优美标号并证明其不是平衡图。
⑸给出当min{p，m}≥2(m，n，p，q为正整数且m≤n，p≤ q)时，图Km,n∪Kp,q的平衡标号。