×

On the monotonicity of \((k;g,h)\)-graphs. (English) Zbl 1013.05041

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 F. Harary and P. Kovács [J. Graph Theory 7, 209-218 (1983; Zbl 0542.05041)].

MSC:

05C38 Paths and cycles
05C75 Structural characterization of families of graphs

Citations:

Zbl 0542.05041
Full Text: DOI

References:

[1] Bondy, J.A., Murty, U.S.R. Graph theory with applications. Macmillan, London and Elsevier, New York, 1976 · Zbl 1226.05083
[2] Chartrand, G., Gould, R.J., Kapoor, S.F. Graphs with prescribed degree sets and girth. Period. Math Hunger., 12: 261–266 (1981) · doi:10.1007/BF01849614
[3] Fu, H.L., Huang, K.C., Rodger, C.A. Connectivity of cages. J. of Graph Theory, 24(2): 187–191 (1997) · Zbl 0866.05035 · doi:10.1002/(SICI)1097-0118(199702)24:2<187::AID-JGT6>3.0.CO;2-M
[4] Harary, F., Kovács, P. Regular graphs with given girth pair. J. of Graph Theory, 7: 209–218 (1983) · Zbl 0542.05041 · doi:10.1002/jgt.3190070210
[5] Tutte, W.T. A family of cubical graphs. Proc. Cambridge Phil. Soc., 459–474 (1947) · Zbl 0029.42401
[6] Wang, P., Xu, B., Wang, J.F. On the Connectivity of cages. submitted to J. of Graph Theory. · Zbl 1071.05546
[7] Wong, P-K Cages-a survey. J. of Graph Theory, 6: 1–22 (1982) · Zbl 0488.05044 · doi:10.1002/jgt.3190060103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.