The aim of this thesis is to study the number of spanning trees in different classes of graphs. We designed a set of experiments centered mainly around regular graphs and examined graphs with the least and most spanning trees for a given category of graphs. We were using genreg, a program that enabled us to acquire even large complete sets of unlabeled k-regular graphs on n vertices which were then processed and evaluated with regard to their number of spanning trees. For each experiment, command line tools were implemented, allowing the user to specify properties of the set of graphs they wish to work with. After having gathered enough data, we proposed a hypothesis about the structure and the number of spanning trees in 3-regular graphs on n vertices with minimum number of spanning trees for given n. We also suggested a trait that seems to be shared between 3-regular graphs with maximum number of spanning trees for a given number of vertices.

Cieľom tejto práce je študovať počet kostier v rôznych triedach grafov. Navrhli sme sadu experimentov, zameraných hlavne na regulárne grafy, a preskúmali sme grafy s najmenším a najväčším počtom kostier v danej kategórii grafov. Používali sme gen- reg, program ktorý nám umožnil získať množiny všetkých neoznačených k-regulárnych grafov na n vrcholoch, ktoré boli následne spracovávané a vyhodnocované vzhľadom na ich počet kostier. Pre každý experiment sme implementovali nástroje príkazového riadku, ktoré umožnujú používateľovi špecifikovať vlastnosti sady grafov, s ktorou si želá pracovať. Keď sme nazbierali dostatok dát, predložili sme hypotézu o štruktúre a počte kostier v 3-regulárnych grafoch na n vrcholoch s najnižším možným počtom kostier pre dané n. Taktiež sme navrhli vlastnosť, ktorá sa zdá byť zdieľaná medzi 3-regulárnymi grafmi s maximálnym počtom kostier pre daný počet vrcholov.