A Database of Graphs in <i>Combinatorica</i> Format

## A Database of Graphs in Combinatorica Format

This page contains several collection of important classes of graphs, all converted to the graph format used by Combinatorica, a package for teaching and research in discrete mathematics, particularly combinatorics and graph theory. See our associated book: Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica by Sriram Pemmaraju and Steven Skiena, Cambridge University Press, 2003 for more information about Combinatorica.

These graphs can be used to test conjectures, by explictly testing whether a given property holds on all small trees, bipartite graphs, etc. Experiments with Random labeled graphs are typically easy to construct, but experiments with them are typically wasteful because isomorphic copies can be repeatedly generated, and unconvincing because they do not systematically look for all possible counter-examples. These graph collections represent complete sets of interesting unlabeled graphs, and permit typically testing all relevant graphs up to a non-trivial number of vertices. For example, the animation above cycles through all 106 unlabeled trees on 10 vertices; by comparison, there are 100,000,00 labeled trees on 10 vertices!

These graphs are converted to Combinatorica format from the originals made available in the compact but unprintable g6 format on Gordon Royle's website. He deserves great thanks for making them available. Larger instances of many graph classes are available on his site. The conversion from g6 format was done using conversion software developed by King Larry Mak at Stony Brook. Graph databases available include

All of these files have been collected into a single 6MB gzipped tarfile for convenient downloading. A Database of Graphs in <i>Combinatorica</i> Format

## A Database of Graphs in Combinatorica Format

This page contains several collection of important classes of graphs, all converted to the graph format used by Combinatorica, a package for teaching and research in discrete mathematics, particularly combinatorics and graph theory.

These graphs can be used to test conjectures, by explictly testing whether a given property holds on all small trees, bipartite graphs, etc. Experiments with Random labeled graphs are typically easy to construct, but experiments with them are typically wasteful because isomorphic copies can be repeatedly generated, and unconvincing because they do not systematically look for all possible counter-examples. These graph collections represent complete sets of interesting unlabeled graphs, and permit typically testing all relevant graphs up to a non-trivial number of vertices. For example, the animation above cycles through all 106 unlabeled trees on 10 vertices; by comparison, there are 100,000,00 labeled trees on 10 vertices!

These graphs are converted to Combinatorica format from the originals made available in the compact but unprintable g6 format on Gordon Royle's website. He deserves great thanks for making them available. Larger instances of many graph classes are available on his site. The conversion from g6 format was done using conversion software developed by King Larry Mak at Stony Brook. Graph databases available include

## Bipartite Graphs

 Vertices 1 2 3 4 5 6 7 2 1 3 1 4 1 2 5 1 4 6 1 6 10 7 1 9 34 8 1 12 76 93 9 1 16 155 558 10 1 20 290 1824 1897

## Trees

 Vertices Number 1 1 2 1 3 1 4 2 5 3 6 6 7 11 8 23 9 47 10 106 11 235 12 551 13 1301 14 3159

## Vertex-critical graphs

 Vertices Number 4 1 5 2 6 1 7 10 8 17 9 370

## Edge-critical graphs

 Edge Number 4 1 5 2 6 1 7 5 8 9 9 47 10 338

## Type-2 Edge Colorable Graphs (Vizing's theorem)

 Vertices Number 5 4 6 3 7 32 8 67 9 930

## Cubic graphs

 Vertices girth>=3 >=5 >=6 >=7 8 5 0 0 0 10 19 1 0 0 12 85 2 0 0 14 509 9 1 0 16 4060 49 1 0 18 41301 455 5 0 20 510489 5783 32 0 22 7319447 90938 385 0 24 117940535 1620479 7574 1 26 2094480864 31478584 181227 3 28 40497138011 4624501 4624501 21 30 2094480864 432757568 122090544 546

## Snarks

 Vertices Cyc-con>=4 >=5 >=6 10 1 1 12 0 0 14 0 0 16 0 0 18 2 0 20 6 1 22 20 2 24 38 2 26 280 10 28 2900 75 1

## Transitive graphs

 Vertices Transitive Caley Connected Transitive Connected Cayley Connected Non-Cayley 1 1 1 0 1 1 0 2 2 2 0 1 1 0 3 2 2 0 1 1 0 4 4 4 0 2 2 0 5 3 3 0 2 2 0 6 8 8 0 5 5 0 7 4 4 0 3 3 0 8 14 14 0 10 10 0 9 9 9 0 7 7 0 10 22 20 2 18 16 2 11 8 8 0 7 7 0 12 74 74 0 64 64 0 13 14 14 0 13 13 0 14 56 56 0 51 51 0 15 48 44 4 44 40 4 16 286 278 8 272 264 8 17 36 36 0 35 35 0 18 380 376 4 365 361 4 19 60 60 0 59 59 0 20 1214 1132 82 1190 1110 80 21 240 240 0 235 235 0 22 816 816 0 807 807 0 23 188 188 0 187 187 0 24 15506 15394 112 15422 15310 112 25 464 464 0 461 461 0 26 4236 4104 132 4221 4089 132 27 1434 1434 0 1425 1425 0 28 25850 25784 66 25792 25726 66 29 1182 1182 0 1181 1181 0 30 46308 45184 1124 46236 45118 1118 31 2192 2192 0 2191 2191 0

## Cubic Transitive Graphs

 Vertices Prime Factorization Symmetric Cayley Non-Cayley Total 68 2, 2, 17 0 11 1 12 70 2, 5, 7 0 11 0 11 72 2, 2, 2, 3, 3 1 36 1 37 74 2, 37 1 8 1 9 76 2, 2, 19 0 11 0 11 78 2, 3, 13 1 14 0 14 80 2, 2, 2, 2, 5 1 29 4 33 82 2, 41 0 8 1 9 84 2, 2, 3, 7 1 27 3 30 86 2, 43 1 9 0 9 88 2, 2, 2, 11 0 16 1 17 90 2, 3, 3, 5 1 18 3 21 92 2, 2, 23 0 13 0 13 94 2, 47 0 9 0 9 96 2, 2, 2, 2, 2, 3 2 90 ? ? 98 2, 7, 7 2 13 0 13 100 2, 2, 5, 5 0 23 2 25 102 2, 3, 17 1 15 1 16 104 2, 2, 2, 13 1 ? ? 22 106 2, 53 0 10 1 11 108 2, 2, 3, 3, 3 1 ? ? 42 110 2, 5, 11 1 19 0 19 112 2, 2, 2, 2, 7 3 ? ? 38 114 2, 3, 19 1 18 0 18 116 2, 2, 29 0 17 1 18 118 2, 59 0 11 0 11 120 2, 2, 2, 3, 5 2 ? ? ? 122 2, 61 1 12 1 13 124 2, 2, 31 0 17 0 17 126 2, 3, 3, 7 1 ? ? 26 128 2, 2, 2, 2, 2, 2, 2 2 82 1 83 130 2, 5, 13 0 17 2 19 132 2, 2, 3, 11 0 ? ? 35 134 2, 67 1 13 0 13 136 2, 2, 2, 17 0 ? ? 28 138 2, 3, 23 0 19 0 19 140 2, 2, 5, 7 0 ? ? ? 142 2, 71 0 13 0 13 144 2, 2, 2, 2, 3, 3 2 ? ? ? 146 2, 73 1 14 1 15 148 2, 2, 37 0 21 1 22 150 2, 3, 5, 5 1 ? ? 28 152 2, 2, 2, 19 1 ? ? 27 154 2, 7, 11 0 19 0 19 156 2, 2, 3, 13 0 ? ? 46 158 2, 79 1 15 0 15 160 2, 2, 2, 2, 2, 5 0 ? ? ? 162 2, 3, 3, 3, 3 3 ? ? ? 164 2, 2, 41 0 23 1 24 166 2, 83 0 15 0 15 168 2, 2, 2, 3, 7 6 ? ? ? 170 2, 5, 17 0 21 2 23 172 2, 2, 43 0 23 0 23 174 2, 3, 29 0 23 0 23 176 2, 2, 2, 2, 11 0 ? ? ? 178 2, 89 0 16 1 17 180 2, 2, 3, 3, 5 0 ? ? ? 182 2, 7, 13 4 23 2 25 184 2, 2, 2, 23 0 ? ? 31 186 2, 3, 31 1 26 0 26 188 2, 2, 47 0 25 0 25 190 2, 5, 19 0 23 0 23 192 2, 2, 2, 2, 2, 2, 3 3 ? ? ? 194 2, 97 1 18 1 19 196 2, 2, 7, 7 0 ? ? 35 198 2, 3, 3, 11 0 ? ? ? 200 2, 2, 2, 5, 5 1 ? ? 61 202 2, 101 0 18 1 19 204 2, 2, 3, 17 1 ? ? 53 206 2, 103 1 19 0 19 208 2, 2, 2, 2, 13 1 ? ? ? 210 2, 3, 5, 7 0 43 ? ? 212 2, 2, 53 0 29 ? 30 214 2, 107 0 19 0 19 216 2, 2, 2, 3, 3, 3 3 ? ? ? 218 2, 109 1 20 1 21 220 2, 2, 5, 11 3 ? ? ? 222 2, 3, 37 1 30 0 30 224 2, 2, 2, 2, 2, 7 3 ? ? ? 226 2, 113 0 20 1 21 228 2, 2, 3, 19 0 ? ? 57 230 2, 5, 23 0 27 0 27 232 2, 2, 2, 29 0 ? ? 40 234 2, 3, 3, 13 2 ? ? ? 236 2, 2, 59 0 31 0 31 238 2, 7, 17 0 27 ? ? 240 2, 2, 2, 2, 3, 5 3 ? ? ? 242 2, 11, 11 1 25 0 25 244 2, 2, 61 0 33 1 34 246 2, 3, 41 0 31 0 31 248 2, 2, 2, 31 1 ? ? 41 250 2, 5, 5, 5 1 ? ? 37 252 2, 2, 3, 3, 7 0 ? ? ? 254 2, 127 1 23 0 23 256 2, 2, 2, 2, 2, 2, 2, 2 4 ? ? 284 258 2, 3, 43 1 34 0 34

## Bipartite Graphs

 Vertices 1 2 3 4 5 6 7 2 1 3 1 4 1 2 5 1 4 6 1 6 10 7 1 9 34 8 1 12 76 93 9 1 16 155 558 10 1 20 290 1824 1897

## Trees

 Vertices Number 1 1 2 1 3 1 4 2 5 3 6 6 7 11 8 23 9 47 10 106 11 235 12 551 13 1301 14 3159

## Vertex-critical graphs

 Vertices Number 4 1 5 2 6 1 7 10 8 17 9 370 10 5530

## Edge-critical graphs

 Edge Number 4 1 5 2 6 1 7 5 8 9 9 47 10 338 11 5649

## Type-2 Edge Colorable Graphs (Vizing's theorem)

 Vertices Number 5 4 6 3 7 32 8 67 9 930

## Cubic graphs

 Vertices girth>=3 >=5 >=6 >=7 8 5 0 0 0 10 19 1 0 0 12 85 2 0 0 14 509 9 1 0 16 4060 49 1 0 18 41301 455 5 0 20 510489 5783 32 0 22 7319447 90938 385 0 24 117940535 1620479 7574 1 26 2094480864 31478584 181227 3 28 40497138011 4624501 4624501 21 30 2094480864 432757568 122090544 546

## Snarks

 Vertices Cyc-con>=4 >=5 >=6 10 1 1 12 0 0 14 0 0 16 0 0 18 2 0 20 6 1 22 20 2 24 38 2 26 280 10 28 2900 75 1

## Transitive graphs

 Vertices Transitive Caley Connected Transitive Connected Cayley Connected Non-Cayley 1 1 1 0 1 1 0 2 2 2 0 1 1 0 3 2 2 0 1 1 0 4 4 4 0 2 2 0 5 3 3 0 2 2 0 6 8 8 0 5 5 0 7 4 4 0 3 3 0 8 14 14 0 10 10 0 9 9 9 0 7 7 0 10 22 20 2 18 16 2 11 8 8 0 7 7 0 12 74 74 0 64 64 0 13 14 14 0 13 13 0 14 56 56 0 51 51 0 15 48 44 4 44 40 4 16 286 278 8 272 264 8 17 36 36 0 35 35 0 18 380 376 4 365 361 4 19 60 60 0 59 59 0 20 1214 1132 82 1190 1110 80 21 240 240 0 235 235 0 22 816 816 0 807 807 0 23 188 188 0 187 187 0 24 15506 15394 112 15422 15310 112 25 464 464 0 461 461 0 26 4236 4104 132 4221 4089 132 27 1434 1434 0 1425 1425 0 28 25850 25784 66 25792 25726 66 29 1182 1182 0 1181 1181 0 30 46308 45184 1124 46236 45118 1118 31 2192 2192 0 2191 2191 0

## Cubic Transitive Graphs

 Vertices Prime Factorization Symmetric Cayley Non-Cayley Total 68 2, 2, 17 0 11 1 12 70 2, 5, 7 0 11 0 11 72 2, 2, 2, 3, 3 1 36 1 37 74 2, 37 1 8 1 9 76 2, 2, 19 0 11 0 11 78 2, 3, 13 1 14 0 14 80 2, 2, 2, 2, 5 1 29 4 33 82 2, 41 0 8 1 9 84 2, 2, 3, 7 1 27 3 30 86 2, 43 1 9 0 9 88 2, 2, 2, 11 0 16 1 17 90 2, 3, 3, 5 1 18 3 21 92 2, 2, 23 0 13 0 13 94 2, 47 0 9 0 9 96 2, 2, 2, 2, 2, 3 2 90 ? ? 98 2, 7, 7 2 13 0 13 100 2, 2, 5, 5 0 23 2 25 102 2, 3, 17 1 15 1 16 104 2, 2, 2, 13 1 ? ? 22 106 2, 53 0 10 1 11 108 2, 2, 3, 3, 3 1 ? ? 42 110 2, 5, 11 1 19 0 19 112 2, 2, 2, 2, 7 3 ? ? 38 114 2, 3, 19 1 18 0 18 116 2, 2, 29 0 17 1 18 118 2, 59 0 11 0 11 120 2, 2, 2, 3, 5 2 ? ? ? 122 2, 61 1 12 1 13 124 2, 2, 31 0 17 0 17 126 2, 3, 3, 7 1 ? ? 26 128 2, 2, 2, 2, 2, 2, 2 2 82 1 83 130 2, 5, 13 0 17 2 19 132 2, 2, 3, 11 0 ? ? 35 134 2, 67 1 13 0 13 136 2, 2, 2, 17 0 ? ? 28 138 2, 3, 23 0 19 0 19 140 2, 2, 5, 7 0 ? ? ? 142 2, 71 0 13 0 13 144 2, 2, 2, 2, 3, 3 2 ? ? ? 146 2, 73 1 14 1 15 148 2, 2, 37 0 21 1 22 150 2, 3, 5, 5 1 ? ? 28 152 2, 2, 2, 19 1 ? ? 27 154 2, 7, 11 0 19 0 19 156 2, 2, 3, 13 0 ? ? 46 158 2, 79 1 15 0 15 160 2, 2, 2, 2, 2, 5 0 ? ? ? 162 2, 3, 3, 3, 3 3 ? ? ? 164 2, 2, 41 0 23 1 24 166 2, 83 0 15 0 15 168 2, 2, 2, 3, 7 6 ? ? ? 170 2, 5, 17 0 21 2 23 172 2, 2, 43 0 23 0 23 174 2, 3, 29 0 23 0 23 176 2, 2, 2, 2, 11 0 ? ? ? 178 2, 89 0 16 1 17 180 2, 2, 3, 3, 5 0 ? ? ? 182 2, 7, 13 4 23 2 25 184 2, 2, 2, 23 0 ? ? 31 186 2, 3, 31 1 26 0 26 188 2, 2, 47 0 25 0 25 190 2, 5, 19 0 23 0 23 192 2, 2, 2, 2, 2, 2, 3 3 ? ? ? 194 2, 97 1 18 1 19 196 2, 2, 7, 7 0 ? ? 35 198 2, 3, 3, 11 0 ? ? ? 200 2, 2, 2, 5, 5 1 ? ? 61 202 2, 101 0 18 1 19 204 2, 2, 3, 17 1 ? ? 53 206 2, 103 1 19 0 19 208 2, 2, 2, 2, 13 1 ? ? ? 210 2, 3, 5, 7 0 43 ? ? 212 2, 2, 53 0 29 ? 30 214 2, 107 0 19 0 19 216 2, 2, 2, 3, 3, 3 3 ? ? ? 218 2, 109 1 20 1 21 220 2, 2, 5, 11 3 ? ? ? 222 2, 3, 37 1 30 0 30 224 2, 2, 2, 2, 2, 7 3 ? ? ? 226 2, 113 0 20 1 21 228 2, 2, 3, 19 0 ? ? 57 230 2, 5, 23 0 27 0 27 232 2, 2, 2, 29 0 ? ? 40 234 2, 3, 3, 13 2 ? ? ? 236 2, 2, 59 0 31 0 31 238 2, 7, 17 0 27 ? ? 240 2, 2, 2, 2, 3, 5 3 ? ? ? 242 2, 11, 11 1 25 0 25 244 2, 2, 61 0 33 1 34 246 2, 3, 41 0 31 0 31 248 2, 2, 2, 31 1 ? ? 41 250 2, 5, 5, 5 1 ? ? 37 252 2, 2, 3, 3, 7 0 ? ? ? 254 2, 127 1 23 0 23 256 2, 2, 2, 2, 2, 2, 2, 2 4 ? ? 284 258 2, 3, 43 1 34 0 34