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)].
Reviewer: Gabriel Semanišin (Košice)
Citations:
Zbl 0542.05041References:
[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.