连通图的顶点k-素标号与不连通图的顶点素标号OA

图的标号是图论中具有实际应用背景的研究课题。根据不同要求,产生了各种类型的标号,顶点素标号是其中的一种,顶点k-素标号是顶点素标号的推广。本文根据素数理论知识分类讨论,用优先圈法及深度优先法,证明了树、单圈图、双圈图、一般连通图都有顶点k-素标号,进而证明了当且仅当不连通图的连通分支中至多有一个奇圈,不连通图有顶点素标号。