Graph details

Graph # 21067

Adjacency matrix

001010000000
000101000000
100000001000
010000000100
100000000001
010000000010
000000001001
000000000110
001000100100
000100011000
000001010001
000010100010

Adjacency list

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

HoG graph id

21067

Graph name

Knight grid 3x4

Graph submitted by

Kevin Ryde

Invariant values

The definitions of the invariants can be found here.
Invariant Value Invariant Value
Acyclic No Index 2.438
Algebraic Connectivity 0.364 Laplacian Largest Eigenvalue 5.066
Average Degree 2.333 Longest Induced Cycle 10
Bipartite Yes Longest Induced Path 8
Chromatic Index 3 Matching Number 6
Chromatic Number 2 Maximum Degree 3
Circumference 10 Minimum Degree 2
Claw-Free No Minimum Dominating Set 4
Clique Number 2 Number of Components 1
Connected Yes Number of Edges 14
Density 0.212 Number of Triangles 0
Diameter 5 Number of Vertices 12
Edge Connectivity 2 Planar Yes
Eulerian No Radius 4
Genus 0 Regular No
Girth 6 Second Largest Eigenvalue 1.757
Hamiltonian No Smallest Eigenvalue -2.438
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 Jun 23, 2015 12:50 AM.
Vertices are squares of a 3x4 chess board. Edges are between squares at a knight move 1,2 or 2,1 apart. Some shifting and twisting makes a planar layout.

Euler gives the 3 distinct knight's tours of this board (and a 4th tour which is a reversal and vertical mirror image of the second). These are Hamiltonian paths (not cycles) on the graph.

Leonhard Euler, "Solution d'une Question Curieuse qui ne Paroit Soumise à Aucune Analyse", Mémoires de l'Académie Royale des Sciences et Belles Lettres de Berlin, volume 15, Année 1759, pages 310-337, published 1766, paragraph 42 page 336.
http://eulerarchive.maa.org/pages/E309.html

Donald Knuth, "Selected Papers on Fun and Games", chapter 42 "Long and Skinny Knight's Tours", pages 511-539.
http://www-cs-faculty.stanford.edu/~uno/fg.html

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