New graphs related to (p,6)(p,6) and (p,8)(p,8)-cages

Constructing regular graphs with a given girth, a given degree and the fewest possible vertices is hard. This problem is called the cage graph problem and has some links with the error code theory. GG-graphs can be used in many applications: symmetric and semi-symmetric graph constructions, (Bretto and Gillibert (2008) [12]), hamiltonicity of Cayley graphs, and so on. In this paper, we show that GG-graphs can be a good tool to construct some upper bounds for the cage problem. For pp odd prime we construct (p,6)(p,6)-graphs which are GG-graphs with orders 2p22p2 and 2p2−22p2−2, when the Sauer bound is equal to 4(p−1)34(p−1)3. We construct also (p,8)(p,8)-GG-graphs with orders 2p32p3 and 2p3−2p2p3−2p, while the Sauer upper bound is equal to 4(p−1)54(p−1)5.