关键词: 双圈图, 优美图, 优美标号

Abstract: Aiming at the bicyclic graphs, we designed an algorithm to determine the gracefulness of graphs verified the gracefulness of all bicyclic graphs with at most 17 vertices, and obtained all graceful and ungraceful graphs in this range. The results show that except ∞shape bicyclic graphs C_(m,n), all bicyclic graphs with at most 17 vertices are graceful, where (m+n)(mod 4)={1,2}. Finally, we gave a proof for the ungracefulness of this kind of graph, and further speculation that the conclusion still held true when the number of vertices was greater than 17.

Key words: bicyclic graph, graceful graph, graceful labeling