“Butterfly graph”的意思、由来-开放百科全书

词条

Butterfly graph

释义

Bowtie-free graphs
Algebraic properties
References

{{Infobox graph
| name = Butterfly graph
| image =
| vertices = 5
| edges = 6
| automorphisms = 8 (D₄)
| diameter = 2
| radius = 1
| girth = 3
| chromatic_number = 3
| chromatic_index = 4
| properties = Planar
Unit distance
Eulerian
Not graceful
}}

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₃ with a common vertex and is therefore isomorphic to the friendship graph F₂.

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 C₅ and the complete graph K₅.^[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 D₄, the group of symmetries of a square, including both rotations and reflections.

The characteristic polynomial of the butterfly graph is .

References

1. ^{{MathWorld|urlname=ButterflyGraph|title=Butterfly Graph}}
2. ^ISGCI: Information System on Graph Classes and their Inclusions. "List of Small Graphs".
3. ^{{mathworld|title=Graceful graph|urlname=GracefulGraph}}
4. ^{{citation | last = Ando | first = Kiyoshi | contribution = Contractible edges in a k-connected graph | doi = 10.1007/978-3-540-70666-3_2 | mr = 2364744 | pages = 10–20 | publisher = Springer, Berlin | series = Lecture Notes in Comput. Sci. | title = Discrete geometry, combinatorics and graph theory | volume = 4381 | year = 2007}}.

2 : Individual graphs|Planar graphs

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。