• Source: 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. 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 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 C5 and the complete graph K5.




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.




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



−
(
x
−
1
)
(
x
+
1

)

2


(

x

2


−
x
−
4
)


{\displaystyle -(x-1)(x+1)^{2}(x^{2}-x-4)}

.




References

Kata Kunci Pencarian:

• Mark Zuckerberg
• Butterfly graph
• Planar graph
• Glossary of graph theory
• Friendship graph
• List of graphs
• Diamond graph
• Hofstadter's butterfly
• Pseudoforest
• Windmill graph
• Butterfly diagram