Pan Graph

The -pan graph is the graph obtained by joining a cycle graph to a singleton graph with a graph 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 tadpole graphs 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 vertex with label 0 in a cycle graph graceful labeling.

Pan graphs are dominating unique.

Precomputed properties of pan graphs are available in the Wolfram Language as GraphData["Pan", n].

The -pan graph has chromatic polynomial

which has recurrence equation