GENREG
Fast generation of regular graphs and construction of cages. The construction of complete lists of regular graphs up to isomorphism is one of the oldest problems in constructive combinatorics. In this article an efficient algorithm to generate regular graphs with a given number of vertices and vertex degree is introduced. The method is based on orderly generation refined by criteria to avoid isomorphism checking and combined with a fast test for canonicity. The implementation allows computing even large classes of graphs, like construction of the 4-regular graphs on 18 vertices and, for the first time, the 5-regular graphs on 16 vertices. Also in cases with given girth, some remarkable results are obtained. For instance, the 5-regular graphs with girth 5 and minimal number of vertices were generated in less than 1,h. There exist exactly four (5,,5)-cages.
Keywords for this software
References in zbMATH (referenced in 48 articles )
Showing results 1 to 20 of 48.
Sorted by year (- Dybizbański, Janusz; Ochem, Pascal; Pinlou, Alexandre; Szepietowski, Andrzej: Oriented cliques and colorings of graphs with low maximum degree (2020)
- Fowler, Patrick W.; Gauci, John Baptist; Goedgebeur, Jan; Pisanski, Tomaž; Sciriha, Irene: Existence of regular nut graphs for degree at most 11 (2020)
- Goedgebeur, Jan; Meersman, Barbara; Zamfirescu, Carol T.: Graphs with few Hamiltonian cycles (2020)
- Kasyoki, Donnie; Oleche, Paul: 4-regular prime graphs of nonsolvable groups (2020)
- Lauri, Juho; Mitillos, Christodoulos: Perfect Italian domination on planar and regular graphs (2020)
- Abreu, Marién; Araujo-Pardo, Gabriela; Balbuena, Camino; Labbate, Domenico: An alternate description of a ((q + 1, 8))-cage (2018)
- Brinkmann, Gunnar: Computing the maximal canonical form for trees in polynomial time (2018)
- Cakiroglu, Sera Aylin: Optimal regular graph designs (2018)
- Haythorpe, Micheal: On the minimum number of Hamiltonian cycles in regular graphs (2018)
- Logan, Adam: New realizations of modular forms in Calabi-Yau threefolds arising from (\phi^4) theory (2018)
- Schauz, Uwe: Computing the list chromatic index of graphs (2018)
- Tuzun, Robert E.; Sikora, Adam S.: Verification of the Jones unknot conjecture up to 22 crossings (2018)
- Abajo, E.; Araujo-Pardo, G.; Balbuena, C.; Bendala, M.: New small regular graphs of girth 5 (2017)
- Brijder, Robert; Traldi, Lorenzo: Isotropic matroids. III: Connectivity (2017)
- Fujita, André; Takahashi, Daniel Yasumasa; Balardin, Joana Bisol; Vidal, Maciel Calebe; Sato, João Ricardo: Correlation between graphs with an application to brain network analysis (2017)
- Goedgebeur, Jan; Zamfirescu, Carol T.: Improved bounds for hypo-Hamiltonian graphs (2017)
- Hoppe, Travis; Petrone, Anna: Integer sequence discovery from small graphs (2016)
- Larrión, F.; Pizaña, M. A.; Villarroel-Flores, R.: On self-clique shoal graphs (2016)
- Abreu, M.; Araujo-Pardo, G.; Balbuena, C.; Labbate, D.: A construction of small ((q-1))-regular graphs of girth 8 (2015)
- Ejov, V.; Haythorpe, M.; Rossomakhine, S.: A linear-size conversion of HCP to 3HCP (2015)