|
The Cage Problem is one of the oldest problems in Graph Theory.
The idea is to find
smallest regular graphs with given degree and
girth and with the minimum possible number of vertices.
A regular graph is one in which every vertex
has the same degree.
The degree of a vertex is the number of edges incident
with it, and the girth of a graph is the length of a shortest cycle.
|
|
The links below point to files containing the
smallest known graphs
for certain values of degree and girth.
Each graph is saved as an adjacency list. The vertices are
labeled with the integers 0 to n-1. Line 1 lists the neighbors
of vertex 0, line 2 the neighbors of vertex 1, etc.
Only my constructions are shown here, for more
complete coverage see the
Dynamic Survey.
|
|
|
New Results:
I recently found a new record (10,5)-graph.
The order of the graph is 124, improving the entry in the
survey (which was 126). The graph can be found
here. It was found using an
algorithm based on a geometric method due to
Abreu, Araujo-Pardo, Balbuena, and Labbate.
|
|
|
Corrections to the Survey:
Recently two omissions in the Dynamic Survey have come to light. The order of
the smallest (13,5)-graph is 230, not 240.
Five such graphs are known and can be found here.
Also, the smallest (11,5)-graph has order 154, not 156. The graph can be seen here.
I discovered these graphs approximately 10 years ago. All six graphs were constructed
by starting with a known (smaller) cage, and carefully adding and deleting individual edges.
- (13,5)-Graph A
- (13,5)-Graph B
- (13,5)-Graph C
- (13,5)-Graph D
- (13,5)-Graph E
- An (11,5)-Graph
|