TOPICS
Search

Pan Graph


PanGraph

The n-pan graph is the graph obtained by joining a cycle graph C_n to a singleton graph K_1 with a bridge. The n-pan graph is therefore isomorphic with the (n,1)-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 (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), thus establishing that pan graphs are graceful.

The fact that the m-pan graphs, corresponding to (m,1)-tadpole graphs, are graceful for m=1, 2 (mod 4) follows immediately from adding the label m+1 to the "handle" vertex adjacent to the verex with label 0 in a cycle graph labeling.

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

The n-pan graph has chromatic polynomial

 pi(x)=(-1)^n(x-1)^2+(x-1)^(n+1),

which has recurrence equation

 p_n(x)=(x-1)p_(n-2)(x)+(x-2)p_(n-1)(x).

See also

Banner Graph, Kayak Paddle Graph, Lollipop Graph, Paw Graph, Tadpole Graph

Explore with Wolfram|Alpha

References

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 B(m,n)." 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.

Referenced on Wolfram|Alpha

Pan Graph

Cite this as:

Weisstein, Eric W. "Pan Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PanGraph.html

Subject classifications