Butterfly graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Butterfly graph
Butterfly graph.svg
Vertices 5
Edges 6
Radius 1
Diameter 2
Girth 3
Automorphisms 8 (D4)
Chromatic number 3
Chromatic index 4
Properties Planar
Unit distance
Eulerian

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.

The butterfly Graph has diameter 2 and girth 3, radius 1, chromatic number 3, chromatic index 4 and is both Eulerian and unit distance. 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[edit]

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, and edge is said 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[edit]

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 -(x-1)(x+1)^2(x^2-x-4).

References[edit]

  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. ^ Kiyoshi Ando "Contractible Edges in a k-Connected Graph", CJCDGCGT 2005: 10-20 [1].