Final Project CSC 422/522, Fall 2014
Bonus Project: CSC 445/545, Fall 2014
Interesting Graphs

To get the sample input files:

interesting.zip

Or you can get them one at a time (more tedious) from here.

The input files:

  1. ic060.txt
  2. icage.txt
  3. ifootball.txt
  4. ihyper.txt
  5. ikneser.txt
  6. iqueen.txt
  7. ivenn.txt
The corresponding output files (after running for two minutes):
  1. oc060.txt
  2. ocage.txt
  3. ofootball.txt
  4. ohyper.txt
  5. okneser.txt
  6. oqueen.txt
  7. ovenn.txt

Fullerenes

Fullerenes correspond to 3-regular planar graphs with face sizes 5 or 6. The input file contains the 1812 fullerenes on 60 vertices.

Cages

A (3,g)-cage is a 3-regular graph of girth g that has a minimum possible number of vertices. This input file contains the small cages. The last two graphs are a girth 13 graph on 272 vertices and a girth 14 graph on 384 vertices; it is not known if these last two graphs are cages or if a smaller graph is possible.

  1. Graph 1: (3,3)-cage on 4 vertices: K4.
  2. Graph 2: (3,4)-cage on 9 vertices: K3,3.
  3. Graph 3: (3,5)-cage on 10 vertices: Petersen graph.
  4. Graph 4: (3,6)-cage on 14 vertices.
  5. Graph 5: (3,7)-cage on 24 vertices.
  6. Graph 6: (3,8)-cage on 30 vertices.
  7. Graphs 7-24: (3,9)-cages on 58 vertices.
  8. Graphs 25-27: (3,10)-cages on 70 vertices.
  9. Graph 28: (3,11)-cage on 112 vertices.
  10. Graph 29: (3,13)-graph.
  11. Graph 30: (3,14)-graph.

Football Pool Problem Graphs

Assume that k soccer matchs are being played. Each one can end in a win, a loss or a tie. The pool sells tickets that correspond to choosing an outcome for each of the k games. You win something if you have a ticket that has at least k-1 correct outcomes. A dominating set corresponds to a subset of the possible tickets that guarantees that at least one ticket wins.

The graph that has 3k vertices, each one corresponding to a possible outcome for all of the matches. Two vertices are adjacent if they differ in one position. The input file has football pool problems ranging from 1 to 6 matchings having respectively 3, 9, 27, 81, 243 or 729 vertices. These graphs are vertex transitive.

Hypercubes

A hypercube of dimension k has 2k vertices and each vertex is labelled with a different k-bit binary string. Two vertices are adjacent if their binary strings differ in one bit position. Hypercubes have been proposed as a good network topology. For n vertices, the degree of each vertex is relatively small (log2(n)). The input file has hypercubes of dimensions 3 to 9 having 8, 16, 32, 64, 128, 256 and 512 vertices. These graphs are vertex transitive.

Queen Graphs

A queen graph of dimension k has k2 vertices, each one corresponding to a square on a k by k chess board. Two vertices are adjacent if their squares lie in the same row, column, diagonal or back diagonal. The input file has the queen graphs for dimensions 4 to 13.

Minimum Dominating Set Orders for the Queen Graphs

The cases in the table are marked with
* to indicate the answer is (n-1)/2.
+ to indicate the answer is the floor of (n+1)/2.
- to indicate the answer is the 1 + floor of (n+1)/2.
Dimension Min
1 1 +
2 1 +
3 1 *
4 2 +
5 3 +
6 3 +
7 4 +
8 5 -
9 5 +
10 5 +
11 5 *
12 6 +
13 7 +
14 8 -
15 9 -
16 9 -
17 9 +
18 9 +
1910 +
20[10 or 11]
2111 +
22[11 or 12]
2312 +
24[12 or 13]
2513 +
26[13 or 14]
2714 +
28[14 or 15]
2915 +
3015 +

Venn Diagram Graphs

There is a beautiful survey on Venn diagrams: Venn Diagrams by Frank Ruskey, Mark Weston, in the Electronic Journal of Combinatorics. The input file has 11672 4-regular planar graphs on 62 vertices. These correspond to Venn diagrams with 6 curves (they have 64 faces).

Kneser Graphs

This wiki page http://mathworld.wolfram.com/KneserGraph.html has a nice description of the Kneser graphs. They are vertex transitive. The number of vertices of each and the degree of each vertex:

  1. Graph 1: n= 10 [ Degree 3]
  2. Graph 2: n= 15 [ Degree 6]
  3. Graph 3: n= 21 [ Degree 10]
  4. Graph 4: n= 35 [ Degree 4]
  5. Graph 5: n= 28 [ Degree 15]
  6. Graph 6: n= 56 [ Degree 10]
  7. Graph 7: n= 36 [ Degree 21]
  8. Graph 8: n= 84 [ Degree 20]
  9. Graph 9: n= 126 [ Degree 5]
  10. Graph 10: n= 45 [ Degree 28]
  11. Graph 11: n= 120 [ Degree 35]
  12. Graph 12: n= 210 [ Degree 15]
  13. Graph 13: n= 55 [ Degree 36]
  14. Graph 14: n= 165 [ Degree 56]
  15. Graph 15: n= 330 [ Degree 35]
  16. Graph 16: n= 462 [ Degree 6]
  17. Graph 17: n= 66 [ Degree 45]
  18. Graph 18: n= 220 [ Degree 84]
  19. Graph 19: n= 495 [ Degree 70]
  20. Graph 20: n= 792 [ Degree 21]

Open Dominating Set problems

As far as I know, the dominating set problem is open for these graphs:

Lower boundUpper boundGraph nameNumber of verticesDegreesInput file
2227Kneser (9,4) 126 5 ikneser_9_4.txt
1420Kneser (10,4) 210 15 ikneser_10_4.txt
1017Kneser (11,4) 330 35 ikneser_11_4.txt
1012Kneser (12,4) 495 70 ikneser_12_4.txt
1011Queen graph: dimension 20 400 57-75 iqueen_20.txt
1112Queen graph: dimension 22 484 63-83 iqueen_22.txt
1213Queen graph: dimension 24 576 69-91 iqueen_24.txt
1314Queen graph: dimension 26 676 75-99 iqueen_26.txt
5864Hypercube dimension 9 512 9 ihyper_9.txt
7173Football Pool problem dimension 6 729 12 ifootball_6.txt

Let me know if you find any other small open problems that I can add to this chart.

CSC 422/522 Final project / maintained by Wendy Myrvold / wendym@csc.UVic.ca / revised Nov. 11, 2014