Walther graph
From HandWiki
| Walther graph | |
|---|---|
 Walther graph | |
| Named after | Hansjoachim Walther |
| Vertices | 25 |
| Edges | 31 |
| Radius | 5 |
| Diameter | 8 |
| Girth | 3 |
| Automorphisms | 1 |
| Chromatic number | 2 |
| Chromatic index | 3 |
| Properties | Bipartite Planar |
| Table of graphs and parameters | |
In the mathematical field of graph theory, the Walther graph, also called the Tutte fragment, is a planar bipartite graph with 25 vertices and 31 edges named after Hansjoachim Walther.[1] It has chromatic index 3, girth 3 and diameter 8.
If the single vertex of degree 1 whose neighbour has degree 3 is removed, the resulting graph has no Hamiltonian path. This property was used by Tutte when combining three Walther graphs to produce the Tutte graph,[2] the first known counterexample to Tait's conjecture that every 3-regular polyhedron has a Hamiltonian cycle.[3]
Algebraic properties
The Walther graph is an identity graph; its automorphism group is the trivial group.
The characteristic polynomial of the Walther graph is :
- [math]\displaystyle{ \begin{align} x^3 \left(x^{22} \right. & {} -31 x^{20}+411 x^{18}-3069 x^{16}+14305 x^{14}-43594 x^{12} \\ & \left. {} +88418 x^{10}-119039 x^8+103929 x^6-55829 x^4+16539 x^2-2040\right) \end{align} }[/math]
References
- ↑ Weisstein, Eric W.. "Walther Graph". http://mathworld.wolfram.com/WaltherGraph.html.
- ↑ Tutte, W. T. (1946), "On Hamiltonian circuits", Journal of the London Mathematical Society 21 (2): 98–101, doi:10.1112/jlms/s1-21.2.98, http://jlms.oxfordjournals.org/cgi/reprint/s1-21/2/98.pdf
- ↑ Tait, P. G. (1884), "Listing's Topologie", Philosophical Magazine, 5th Series 17: 30–46. Reprinted in Scientific Papers, Vol. II, pp. 85–98.
 |  |
