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

Biparite graphs on up to 10 vertices
Trees on up to 14 vertices
Vertex-critical graphs on up to 10 vertices
Edge-critical graphs on up to 11 vertices
Type-2 edge colorable graphs (Vizing's theorem) on up to 9 vertices
Cubic graphs on up to 18 vertices
Snarks on up to 26 vertices.
Transitive graphs on up to 19 vertices.
Cubic transitive graphs on up to 258 vertices.

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

Biparite graphs on up to 10 vertices
Trees on up to 14 vertices
Vertex-critical graphs on up to 10 vertices
Edge-critical graphs on up to 11 vertices
Type-2 edge colorable graphs (Vizing's theorem) on up to 9 vertices
Cubic graphs on up to 18 vertices
Snarks on up to 26 vertices.
Transitive graphs on up to 19 vertices.
Cubic transitive graphs on up to 258 vertices.

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