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


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

ClawFree

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/16713h/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 1573927449, chapter 12, pages 90101.
You need to be logged in to be able to add comments.