New graphs related to (p, 6) and (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. G-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 G-graphs can be a good tool to construct some upper bounds for the cage problem. For p odd prime we construct (p, 6)-graphs which are G-graphs with orders 2p(2) and 2p(2) - 2, when the Sauer bound is equal to 4(p - 1)(3). We construct also (p, 8)-G-graphs with orders 2p(3) and 2p(3) - 2p, while the Sauer upper bound is equal to 4(p - 1)(5). (C) 2011 Elsevier Ltd. All rights reserved.