Butterfly graph

Butterfly graph
Butterfly graph
Vertices	5
Edges	6
Radius	1
Diameter	2
Girth	3
Automorphisms	8 (D4)
Chromatic number	3
Chromatic index	4
Properties	Planar; Unit distance; Eulerian; Not graceful
	Table of graphs and parameters

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 $C 3$ with a common vertex and is therefore isomorphic to the friendship graph $F 2$ .

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 three non-graceful simple graphs with five vertices. One of them is the butterfly graph. The two others are cycle graph $C 5$ and the complete graph $K 5$ .[3]

It often can serve as a simple counterexample to many seemingly intuitive ideas in graph theory.

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 D₄, 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

Weisstein, Eric W. "Butterfly Graph". MathWorld.
ISGCI: Information System on Graph Classes and their Inclusions. "List of Small Graphs".
Weisstein, Eric W. "Graceful graph". MathWorld.
Ando, Kiyoshi (2007), "Contractible edges in a k-connected graph", Discrete geometry, combinatorics and graph theory, Lecture Notes in Comput. Sci., vol. 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.

[1] Weisstein, Eric W. "Butterfly Graph". MathWorld.

[2] ISGCI: Information System on Graph Classes and their Inclusions. "List of Small Graphs".

[Mat2007-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., vol. 4381, Springer, Berlin, pp. 10–20, doi:10.1007/978-3-540-70666-3_2, MR 2364744.