The -pan graph is the graph obtained by joining
a cycle graph to a singleton graph with a bridge.
The -pan graph is therefore isomorphic with
the -tadpole
graph. The special case of the 3-pan graph is sometimes known as the paw
graph and the 4-pan graph as the banner graph
(ISGCI).
Koh et al. (1980) showed that -tadpole graphs are graceful
for , 1, or 3 (mod 4) and conjectured that
all tadpole graphs are graceful (Gallian 2018).
Guo (1994) apparently completed the proof by filling in the missing case in the process
of showing that tadpoles are graceful when or 2 (mod 4) (Gallian 2018), thus establishing that pan
graphs are graceful.
The fact that the -pan
graphs, corresponding to -tadpole
graphs, are graceful for ,
2 (mod 4) follows immediately from adding the label to the "handle" vertex adjacent to the verex with
label 0 in a cycle graph labeling.
Brandstädt, A.; Le, V. B.; and Spinrad, J. P. Graph
Classes: A Survey. Philadelphia, PA: SIAM, pp. 18-19, 1987.Gallian,
J. "Dynamic Survey of Graph Labeling." Elec. J. Combin.DS6.
Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Guo,
W. F. "Gracefulness of the Graph ." J. Inner Mongolia Normal Univ., 24-29,
1994.ISGCI: Information System on Graph Class Inclusions v2.0. "List
of Small Graphs." http://www.graphclasses.org/smallgraphs.html.Koh,
K. M.; Rogers, D. G.; Teo, H. K.; and Yap, K. Y. "Graceful
Graphs: Some Further Results and Problems." Congr. Numer.29,
559-571, 1980.