TOPICS
Search

Butterfly Graph


ButterflyGraphImage

"The" butterfly graph is a name sometimes given to the 5-vertex graph illustrated above. This graph is also known as the "bowtie graph" (West 2000, p. 12) and is the triangular snake graph TS_5. The butterfly graph is ungraceful (Horton 2003). It is implemented in the Wolfram Language as GraphData["ButterflyGraph"].

ButterflyGraph

A different type of butterfly graph is defined as follows. The n-dimensional butterfly graph is a directed graph whose vertices are pairs (w,i), where w is a binary string of length n and i is an integer in the range 0 to n and with directed edges from vertex (w,i) to (w^',i+1) iff w^' is identical to w in all bits with the possible exception of the (i+1)th bit counted from the left.

The n-dimensional butterfly graph has 2^n(n+1) vertices and 2^(n+1)n edges, and can be generated in the Wolfram Language using ButterflyGraph[n, b] (with b=2).


See also

Butterfly Polyiamond, Cricket Graph, Moth Graph, Triangular Snake Graph

Explore with Wolfram|Alpha

References

Horton, M. "Graceful Trees: Statistics and Algorithms." Bachelor of Computing with Honours thesis. University of Tasmania, 2003. https://eprints.utas.edu.au/19/1/GracefulTreesStatisticsAndAlgorithms.pdf.Leighton, F. T. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. San Mateo, CA: Kaufmann, 1992.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, 2003.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 12, 2000.

Cite this as:

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

Subject classifications