Graph details

Graph # 32237

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

HoG graph id

32237

Graph name

Dudeney puzzle "The Cyclists' Tour"

Graph submitted by

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.