Butterfly graph

In the mathematical field of graph theory, the butterfly graph (also called the bowtie graph and the hourglass graph) is a planar undirected graph with 5 vertices and 6 edges.[1][2] It can be constructed by joining 2 copies of the cycle graph C3 with a common vertex and is therefore isomorphic to the friendship graph F2.

Butterfly graph
Vertices5
Edges6
Radius1
Diameter2
Girth3
Automorphisms8 (D4)
Chromatic number3
Chromatic index4
PropertiesPlanar
Unit distance
Eulerian
Not graceful
Table of graphs and parameters

The butterfly graph has diameter 2 and girth 3, radius 1, chromatic number 3, chromatic index 4 and is both Eulerian and a penny graph (this implies that it is unit distance and planar). It is also a 1-vertex-connected graph and a 2-edge-connected graph.

There are only 3 non-graceful simple graphs with five vertices. One of them is the butterfly graph. The two others are cycle graph C5 and the complete graph K5.[3]

Bowtie-free graphs

A graph is bowtie-free if it has no butterfly as an induced subgraph. The triangle-free graphs are bowtie-free graphs, since every butterfly contains a triangle.

In a k-vertex-connected graph, an edge is said to be k-contractible if the contraction of the edge results in a k-connected graph. Ando, Kaneko, Kawarabayashi and Yoshimoto proved that every k-vertex-connected bowtie-free graph has a k-contractible edge.[4]

Algebraic properties

The full automorphism group of the butterfly graph is a group of order 8 isomorphic to the Dihedral group D4, the group of symmetries of a square, including both rotations and reflections.

The characteristic polynomial of the butterfly graph is .

References
  1. Weisstein, Eric W. "Butterfly Graph". MathWorld.
  2. ISGCI: Information System on Graph Classes and their Inclusions. "List of Small Graphs".
  3. Weisstein, Eric W. "Graceful graph". MathWorld.
  4. Ando, Kiyoshi (2007), "Contractible edges in a k-connected graph", Discrete geometry, combinatorics and graph theory, Lecture Notes in Comput. Sci., 4381, Springer, Berlin, pp. 10–20, doi:10.1007/978-3-540-70666-3_2, MR 2364744.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.