Graph details

Graph # 44075

Adjacency matrix

[Too large to display]

Adjacency list

[Too large to display]

HoG graph id


Graph name

Hanoi graph 2 discs, 5 spindles

Graph submitted by

Kevin Ryde

Invariant values

The definitions of the invariants can be found here.
Invariant Value Invariant Value
Acyclic No Index 6.606
Algebraic Connectivity 2.209 Laplacian Largest Eigenvalue 9
Average Degree 6.4 Longest Induced Cycle 10
Bipartite No Longest Induced Path 9
Chromatic Index 7 Matching Number 12
Chromatic Number 5 Maximum Degree 7
Circumference 25 Minimum Degree 4
Claw-Free Yes Minimum Dominating Set 5
Clique Number 5 Number of Components 1
Connected Yes Number of Edges 80
Density 0.267 Number of Triangles 70
Diameter 3 Number of Vertices 25
Edge Connectivity 4 Planar Computation time out
Eulerian No Radius 3
Genus Computation time out Regular No
Girth 3 Second Largest Eigenvalue 3.773
Hamiltonian Yes Smallest Eigenvalue -2
Independence Number 5 Vertex Connectivity 4

A table row rendered like this indicates that the graph is marked as being interesting for that invariant.


Posted by Kevin Ryde at Dec 15, 2020 8:41 AM.
Each vertex is a configuration of discs on spindles for a variation on the Towers of Hanoi puzzle with 2 discs on 5 spindles.

The degree-4 vertices are where the 2 discs are on the same spindle so only the smaller disc can move. The complete-5 clique at each of those is the small disc moving among the 5 spindles. The cross connections between these subgraphs are where the big disc moves (to one of the spindles different from itself and the smaller disc).

You need to be logged in to be able to add comments.