logo

HIST-critical graphs

A homeomorphically irreducible spanning tree or HIST is a spanning tree without vertices of degree 2. A graph not containing a HIST is HIST-free. A graph G is HIST-critical if it is HIST-free and G-v contains a HIST for every vertex v of G.

The graph lists are currently only available in 'graph6' format.

The following lists are available:

All results were obtained with the program HistChecker , see [1] for details.

HIST-critical graphs
VerticesGirth ≥ 3Girth ≥ 4Girth ≥ 5Girth ≥ 6Girth ≥ 7
310000
400000
500000
600000
720000
800000
920000
1000000
11353100
1200000
131536200
14?1100
15?1492500
16?3000
17??24400
18??100
19??412940
20??310
21???980
22???00
23???60360
24???520
25????0
26????0
27????8
Go to top

Planar HIST-critical graphs
VerticesNo. of graphs
31
40
50
60
72
80
90
100
1112
120
1312
140
Go to top

References

[1] J. Goedgebeur, K. Noguchi, J. Renders and C.T. Zamfirescu, HIST-Critical Graphs and Malkevitch’s Conjecture, manuscript.


Copyright © 2010-2024 Ghent University & KU Leuven

Our website uses functional cookies to enhance your user experience. By using this site, you agree to our use of cookies. Learn more

Close