Graph details

Graph # 32239

Adjacency matrix

[Too large to display]

Adjacency list

[Too large to display]

HoG graph id


Graph name

Dudeney puzzle "Visiting the Towns"

Graph submitted by

Kevin Ryde

Invariant values

The definitions of the invariants can be found here.
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.

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