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.