## Adjacency matrix[Too large to display] |
## Adjacency list[Too large to display] |

44075

Hanoi graph 2 discs, 5 spindles

Kevin Ryde

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).

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.