The Computational Challenge of Constructing Cages and (k, g)-Graphs

Gabriela-Araujo Pardo (), Jesús A. De Loera (), Ana Paulina Figueroa, Adjani Gamma-Dessavre and Edgar Possani ()
Additional contact information
Gabriela-Araujo Pardo: UNAM, Instituto de Matematicas
Jesús A. De Loera: University of California, Department of Mathematics
Ana Paulina Figueroa: ITAM, Department of Mathematics
Adjani Gamma-Dessavre: ITAM, Department of Mathematics
Edgar Possani: ITAM, Department of Mathematics

A chapter in Handbook of Visual, Experimental and Computational Mathematics, 2026, pp 793-811 from Springer

Abstract: Abstract The cage problem is the challenging problem of constructing graphs with the least number of vertices having the following properties: the graph most be k-regular (every vertex most has k neighbors); and the girth of a graph most be g (the minimum length of a cycle in the graph must be g). We say that a k-regular graph with girth g is a ( k , g ) $$(k, g)$$ -graph, and thus the cage problem is finding a ( k , g ) $$(k, g)$$ -graph with least number of vertices. This is an interesting problem not only for graph theorists but also for computer scientists, as it has several engineering applications and requires new computational approaches to discover more cages. A matheuristic is an optimization algorithm that combines linear programming models with metaheuristic techniques. In this chapter we review approaches to find cages, and propose a matheuristic to construct ( k , g ) $$(k,g)$$ -graphs with a small number of vertices using integer programming. We show this methodology is able to find cages within reasonable computational times using limited resources.

Keywords: Cages; (k; g)-graphs; Linear programming; Cycle elimination; Matheuristics; LDPC codes; Edge data center organization (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-032-16368-4_56

Ordering information: This item can be ordered from
http://www.springer.com/9783032163684

DOI: 10.1007/978-3-032-16368-4_56

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().