G-graphs for the cage problem
Alain Bretto, Luc Gillibert · 2007
Constructing some regular graph with a given girth,a given degree and the fewest possible vertices is a hard problem. This problem is called the cage graph problem and has some links with the error codes theory. In this paper we presents some new graphs, constructed from a group, with a girth of 6 and regular of degree p, for any prime number p. This graphs are of order 2 x p2 when the best upper bound known for the (p,6)-cage problem was the Sauer bound, equal to 4(p -- 1)3.