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.

References in zbMATH (referenced in 46 articles )

Showing results 1 to 20 of 46.
Sorted by year (citations)

1 2 3 next

  1. Dybizbański, Janusz; Ochem, Pascal; Pinlou, Alexandre; Szepietowski, Andrzej: Oriented cliques and colorings of graphs with low maximum degree (2020)
  2. Fowler, Patrick W.; Gauci, John Baptist; Goedgebeur, Jan; Pisanski, Tomaž; Sciriha, Irene: Existence of regular nut graphs for degree at most 11 (2020)
  3. Goedgebeur, Jan; Meersman, Barbara; Zamfirescu, Carol T.: Graphs with few Hamiltonian cycles (2020)
  4. Abreu, Marién; Araujo-Pardo, Gabriela; Balbuena, Camino; Labbate, Domenico: An alternate description of a ((q + 1, 8))-cage (2018)
  5. Brinkmann, Gunnar: Computing the maximal canonical form for trees in polynomial time (2018)
  6. Cakiroglu, Sera Aylin: Optimal regular graph designs (2018)
  7. Haythorpe, Micheal: On the minimum number of Hamiltonian cycles in regular graphs (2018)
  8. Logan, Adam: New realizations of modular forms in Calabi-Yau threefolds arising from (\phi^4) theory (2018)
  9. Schauz, Uwe: Computing the list chromatic index of graphs (2018)
  10. Tuzun, Robert E.; Sikora, Adam S.: Verification of the Jones unknot conjecture up to 22 crossings (2018)
  11. Abajo, E.; Araujo-Pardo, G.; Balbuena, C.; Bendala, M.: New small regular graphs of girth 5 (2017)
  12. Brijder, Robert; Traldi, Lorenzo: Isotropic matroids. III: Connectivity (2017)
  13. 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)
  14. Goedgebeur, Jan; Zamfirescu, Carol T.: Improved bounds for hypo-Hamiltonian graphs (2017)
  15. Hoppe, Travis; Petrone, Anna: Integer sequence discovery from small graphs (2016)
  16. Larrión, F.; Pizaña, M. A.; Villarroel-Flores, R.: On self-clique shoal graphs (2016)
  17. Abreu, M.; Araujo-Pardo, G.; Balbuena, C.; Labbate, D.: A construction of small ((q-1))-regular graphs of girth 8 (2015)
  18. Ejov, V.; Haythorpe, M.; Rossomakhine, S.: A linear-size conversion of HCP to 3HCP (2015)
  19. Filar, Jerzy A.; Haythorpe, Michael; Rossomakhine, Serguei: A new heuristic for detecting non-Hamiltonicity in cubic graphs (2015)
  20. Goedgebeur, Jan: A counterexample to the pseudo 2-factor isomorphic graph conjecture (2015)

1 2 3 next