The -tadpole graph, also called a dragon
graph (Truszczyński 1984) or kite graph (Kim and Park 2006), is the graph obtained
by joining a cycle graph
to a path graph
with a bridge.
The -tadpole graph is sometimes known
as the
-pan graph. The particular cases of the
- and
-tadpole graphs are also known as the paw
graph and banner graph, respectively (ISGCI).
Precomputed properties of tadpole graphs are available in the Wolfram Language as GraphData["Tadpole",
m, n
].
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).