Tadpole Graph


The (m,n)-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 C_m to a path graph P_n with a bridge.

The (m,1)-tadpole graph is sometimes known as the m-pan graph. The particular cases of the (3,1)- and (4,1)-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 (m,n)-tadpole graphs are graceful for m=0, 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 m=1 or 2 (mod 4) (Gallian 2018).

See also

Banner Graph, Barbell Graph, Kayak Paddle Graph, Lollipop Graph, Pan Graph, Paw Graph

Explore with Wolfram|Alpha


More things to try:


Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018., W. F. "Gracefulness of the Graph B(m,n)." J. Inner Mongolia Normal Univ., 24-29, 1994.ISGCI: Information System on Graph Class Inclusions v2.0. "List of Small Graphs.", S.-R. and Park, J. Y. "On Super Edge-Magic Graphs." Ars Combin. 81, 113-127, 2006.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.Truszczyński, M. "Graceful Unicyclic Graphs." Demonstatio Math. 17, 377-387, 1984.

Referenced on Wolfram|Alpha

Tadpole Graph

Cite this as:

Weisstein, Eric W. "Tadpole Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications