On the monotonicity of \((k;g,h)\)-graphs (Q1862823): Difference between revisions

A \(k\)-regular graph with girth \(g\) is called a \((k;g)\)-graph. A \((k;g)\)-cage is a \((k;g)\)-graph with the least possible number of vertices. The number of vertices of a \((k;g)\)-cage is denoted by \(f(k;g)\). The odd and even girths of a graph \(G\) are the lengths of a shortest odd and even cycle of \(G\) respectively. A \(k\)-regular graph with odd and even girths \(g\) and \(h\) (\(g\) is the smaller of the numbers of odd and even girths) is called a \((k;g,h)\)-graph. A \((k;g,h)\)-cage is a \((k;g,h)\)-graph with the least possible number of vertices. The number of vertices of a \((k;g,h)\)-cage is denoted by \(f(k;g,h)\). It is proved that \(f(k;h-1,h)<f(k;h)\) for \(k\geq 3, h\geq 4\). This result strengthens an inequality proved by \textit{F. Harary} and \textit{P. Kovács} [J. Graph Theory 7, 209-218 (1983; Zbl 0542.05041)].