Butterfly Graph
"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 
. The butterfly graph is ungraceful (Horton 2003). It is implemented in the Wolfram Language as GraphData["ButterflyGraph"].
A different type of butterfly graph is defined as follows. The 
-dimensional butterfly graph is a directed graph whose vertices are pairs 
, where 
is a binary string of length 
and 
is an integer in the range 0 to 
and with directed edges from vertex 
to 
iff 
is identical to 
in all bits with the possible exception of the 
th bit counted from the left.
The 
-dimensional butterfly graph has 
vertices and 
edges, and can be generated in the Wolfram Language using ButterflyGraph[n, b] (with 
).
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.
