Graph details

Adjacency matrix

 000100000001 001000000010 010000100000 100000010000 000000100100 000000011000 001010000010 000101000001 000001000101 000010001010 010000100101 100000011010

Adjacency list

 1: 4 12 2: 3 11 3: 2 7 4: 1 8 5: 7 10 6: 8 9 7: 3 5 11 8: 4 6 12 9: 6 10 12 10: 5 9 11 11: 2 7 10 12 12: 1 8 9 11

32237

Graph name

Dudeney puzzle "The Cyclists' Tour"

Kevin Ryde

Invariant values

The definitions of the invariants can be found here.
Invariant Value Invariant Value
Acyclic No Index 2.906
Algebraic Connectivity 0.355 Laplacian Largest Eigenvalue 6.25
Average Degree 2.667 Longest Induced Cycle 4
Bipartite Yes Longest Induced Path 9
Chromatic Index 4 Matching Number 6
Chromatic Number 2 Maximum Degree 4
Circumference 12 Minimum Degree 2
Claw-Free No Minimum Dominating Set 4
Clique Number 2 Number of Components 1
Connected Yes Number of Edges 16
Density 0.242 Number of Triangles 0
Diameter 5 Number of Vertices 12
Edge Connectivity 2 Planar Yes
Eulerian No Radius 3
Genus 0 Regular No
Girth 4 Second Largest Eigenvalue 2.134
Hamiltonian Yes Smallest Eigenvalue -2.906
Independence Number 6 Vertex Connectivity 2

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

Comments

Posted by Kevin Ryde at Nov 10, 2018 5:39 AM.
Dudeney gives this graph in a puzzle. Vertices are towns and edges are roads between them. The cyclists are to go from top left to top right as drawn here, and visit all other towns exactly once, so a Hamiltonian path. The puzzle is drawn winding around to make it harder than what is just a partial grid. The solution is unique. A Hamiltonian cycle also exists and is unique.

Henry Ernest Dudeney, "Amusements in Mathematics", 1917, puzzle 248 "The Cyclists' Tour".
http://www.gutenberg.org/ebooks/16713
http://www.gutenberg.org/files/16713/16713-h/images/q248.png

Reproduced in Martin Gardner, "The Travelling Salesman", Discover magazine, April 1985. And that article reprinted in Martin Gardner, "Gardner's Whys and Wherefores", Prometheus Books, 1999, ISBN 1-57392-744-9, chapter 12, pages 90-101.

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