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

32239

Dudeney puzzle "Visiting the Towns"

Kevin Ryde

Invariant | Value | Invariant | Value |
---|---|---|---|

Acyclic | No | Index | 3.071 |

Algebraic Connectivity | 0.764 | Laplacian Largest Eigenvalue | 6.457 |

Average Degree | 2.875 | Longest Induced Cycle | 10 |

Bipartite | Yes | Longest Induced Path | 10 |

Chromatic Index | 4 | Matching Number | 8 |

Chromatic Number | 2 | Maximum Degree | 4 |

Circumference | 16 | Minimum Degree | 2 |

Claw-Free | No | Minimum Dominating Set | 4 |

Clique Number | 2 | Number of Components | 1 |

Connected | Yes | Number of Edges | 23 |

Density | 0.192 | Number of Triangles | 0 |

Diameter | 5 | Number of Vertices | 16 |

Edge Connectivity | 2 | Planar | No |

Eulerian | No | Radius | 4 |

Genus | 1 | Regular | No |

Girth | 4 | Second Largest Eigenvalue | 2.029 |

Hamiltonian | Yes | Smallest Eigenvalue | -3.071 |

Independence Number | 8 | Vertex Connectivity | 2 |

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

Posted by Kevin Ryde at Nov 10, 2018 5:54 AM.

Dudeney gives this graph in a puzzle. Vertices are towns and edges are roads between them. The traveller is to visit each town once only, starting and ending at the same place, so a Hamiltonian cycle. Per Dudeney's solution, the degree-2 vertices force a unique Hamiltonian cycle.

Henry Ernest Dudeney, "Amusements in Mathematics", 1917, puzzle 243 "Visiting the Towns", pages 70, 198.

http://www.gutenberg.org/ebooks/16713

Henry Ernest Dudeney, "Amusements in Mathematics", 1917, puzzle 243 "Visiting the Towns", pages 70, 198.

http://www.gutenberg.org/ebooks/16713

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