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 60 articles )

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

1 2 3 next

  1. Brinkmann, Gunnar; Chiers, Sara; Zamfirescu, Carol T.: On 2-factors splitting an embedded graph into two plane graphs (2022)
  2. Brinkmann, Gunnar; Goedgebeur, Jan; Mckay, Brendan D.: The minimality of the Georges-Kelmans graph (2022)
  3. Fabrici, Igor; Madaras, Tomáš; Timková, Mária; Van Cleemput, Nico; Zamfirescu, Carol T.: Non-Hamiltonian graphs in which every edge-contracted subgraph is Hamiltonian (2021)
  4. Jajcay, Robert; Raiman, Tom: Spectra of orders for (k)-regular graphs of girth (g) (2021)
  5. Richter, Hendrik: Spectral analysis of transient amplifiers for death-birth updating constructed from regular graphs (2021)
  6. Samodivkin, Vladimir: Excellent graphs with respect to domination: subgraphs induced by minimum dominating sets (2021)
  7. Zhao, Da: Classification of partially metric Q-polynomial association schemes with (m_1=4) (2021)
  8. Clancy, Kieran; Haythorpe, Michael; Newcombe, Alex; Pegg, Ed jun.: There are no cubic graphs on 26 vertices with crossing number 10 or 11 (2020)
  9. Dybizbański, Janusz; Ochem, Pascal; Pinlou, Alexandre; Szepietowski, Andrzej: Oriented cliques and colorings of graphs with low maximum degree (2020)
  10. Fowler, Patrick W.; Gauci, John Baptist; Goedgebeur, Jan; Pisanski, Tomaž; Sciriha, Irene: Existence of regular nut graphs for degree at most 11 (2020)
  11. Goedgebeur, Jan; Meersman, Barbara; Zamfirescu, Carol T.: Graphs with few Hamiltonian cycles (2020)
  12. Haymaker, Kathryn; O’Pella, Justin: Locally recoverable codes from planar graphs (2020)
  13. Kamil, I. A.; Sudani, H. H. K.; Lobov, A. A.; Abrosimov, M. B.: Constructing all nonisomorphic supergraphs with isomorphism rejection (2020)
  14. Kasyoki, Donnie; Oleche, Paul: 4-regular prime graphs of nonsolvable groups (2020)
  15. Lauri, Juho; Mitillos, Christodoulos: Perfect Italian domination on planar and regular graphs (2020)
  16. Richter, Hendrik: Evolution of cooperation for multiple mutant configurations on all regular graphs with (N \leq14) players (2019)
  17. Abreu, Marién; Araujo-Pardo, Gabriela; Balbuena, Camino; Labbate, Domenico: An alternate description of a ((q + 1, 8))-cage (2018)
  18. Brinkmann, Gunnar: Computing the maximal canonical form for trees in polynomial time (2018)
  19. Cakiroglu, Sera Aylin: Optimal regular graph designs (2018)
  20. Haythorpe, Micheal: On the minimum number of Hamiltonian cycles in regular graphs (2018)

1 2 3 next