Goldner–Harary graph
Goldner–Harary graph | ||
---|---|---|
Chromatic index 8 | | |
Properties | Polyhedral Planar Chordal Perfect Treewidth 3 | |
Table of graphs and parameters |
In the
Properties
The Goldner–Harary graph is a
The Goldner–Harary graph is also
As a non-Hamiltonian maximal planar graph, the Goldner–Harary graph provides an example of a planar graph with book thickness greater than two.[5] Based on the existence of such examples, Bernhart and Kainen conjectured that the book thickness of planar graphs could be made arbitrarily large, but it was subsequently shown that all planar graphs have book thickness at most four.[6]
It has
It is also a 3-tree, and therefore it has treewidth 3. Like any k-tree, it is a chordal graph. As a planar 3-tree, it forms an example of an Apollonian network.
Geometry
By
![Geometric realization of the Goldner–Harary graph](http://upload.wikimedia.org/wikipedia/commons/thumb/4/47/GoldnerHararyJmol2C.jpg/220px-GoldnerHararyJmol2C.jpg)
Geometrically, a polyhedron representing the Goldner–Harary graph may be formed by gluing a tetrahedron onto each face of a
Algebraic properties
The
The characteristic polynomial of the Goldner–Harary graph is : .
References
- ^ Goldner, A.; Harary, F. (1975), "Note on a smallest nonhamiltonian maximal planar graph", Bull. Malaysian Math. Soc., 6 (1): 41–42. See also the same journal 6(2):33 (1975) and 8:104-106 (1977). Reference from listing of Harary's publications.
- .
- ^ Read, R. C.; Wilson, R. J. (1998), An Atlas of Graphs, Oxford, England: Oxford University Press, p. 285.
- ^ ISBN 978-0-387-40409-7.
- . See in particular Figure 9.
- S2CID 5359519.
- S2CID 122755203.
External links
![](http://upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)