×

Monotonicity of the order of \((D;g)\)-cages. (English) Zbl 1234.05060

Summary: A \((D;g)\)-cage is a graph having degree set \(D\), girth \(g\), and the minimum possible number of vertices, which is denoted by \(n(D;g)\). When \(D=\{r\}\) the corresponding \((\{r\};g)\)-cage is clearly \(r\)-regular, and is called an \((r;g)\)-cage. In this work we prove that if \(g<g^{\prime}\) then \(n(D;g)<n(D;g^{\prime})\) under certain requirements on the elements of the degree set \(D\) or on the girth \(g\).

MSC:

05C07 Vertex degrees

Keywords:

cage; degree set; girth
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman and Hall: Chapman and Hall London · Zbl 0890.05001
[2] Tutte, W. T., A family of cubical graphs, Proc. Cambridge Philos. Soc., 43, 459-474 (1947) · Zbl 0029.42401
[3] Erdős, P.; Sachs, H., Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 12, 251-257 (1963) · Zbl 0116.15002
[4] Holton, D. A.; Sheehan, J., The Petersen Graph (1993), Cambridge University Press, (Chapter 6) Cages · Zbl 0781.05001
[5] Wong, P. K., Cages—a survey, J. Graph Theory, 6, 1-22 (1982) · Zbl 0488.05044
[6] Exoo, G.; Jajcay, R., Dynamic cage survey, Electron. J. Combin., 15, #DS16 (2008)
[7] Sauer, N., Extremaleigenschaften regulärer Graphen gegebener Taillenweite. I, II., Österreich. Akad. Wiss. Math.-Natur. Kl. S.-B. II, 176, 27-43 (1967) · Zbl 0159.25401
[8] Daven, M.; Rodger, C. A., \((k; g)\)-cages are 3-connected, Discrete Math., 199, 207-215 (1999) · Zbl 0927.05050
[9] Fu, H. L.; Huang, K. C.; Rodger, C. A., Connectivity of cages, J. Graph Theory, 24, 187-191 (1997) · Zbl 0866.05035
[10] Jiang, T.; Mubayi, D., Connectivity and separating sets of cages, J. Graph Theory, 29, 35-44 (1998) · Zbl 0919.05038
[11] Lin, Y.; Miller, M.; Balbuena, C., Improved lower bound for the vertex connectivity of \((\delta; g)\)-cages, Discrete Math., 299, 162-171 (2005) · Zbl 1080.05053
[12] Marcote, X.; Balbuena, C.; Pelayo, I., On the connectivity of cages with girth five, six and eight, Discrete Math., 307, 1441-1446 (2007) · Zbl 1118.05054
[13] Marcote, X.; Balbuena, C.; Pelayo, I.; Fàbrega, J., \((\delta, g)\)-cages with \(g \geq 10\) are 4-connected, Discrete Math., 301, 124-136 (2005) · Zbl 1079.05049
[14] Xu, B.; Wang, P.; Wang, J. F., On the connectivity of \((4, g)\)-cages, Ars Combin., 64, 181-192 (2002) · Zbl 1071.05546
[15] Balbuena, C.; Marcote, X., Diameter and connectivity of \((D; g)\)-cages, Int. J. Comput. Math., 88, 7, 1387-1397 (2011) · Zbl 1220.05068
[16] Downs, M.; Gould, R. J.; Mitchem, J.; Saba, F., \((D; n)\)-cages, Congr. Numer., 32, 179-193 (1981) · Zbl 0489.05033
[17] Kapoor, S. F.; Polimeni, A. D.; Wall, C. E., Degree sets for graphs, Fund. Math., 95, 189-194 (1977) · Zbl 0351.05129
[18] Chartrand, G.; Gould, R. J.; Kapoor, S. F., Graphs with prescribed degree sets and girth, Period. Math. Hungar., 12, 4, 261-266 (1981) · Zbl 0449.05038
[19] Araujo-Pardo, G.; Balbuena, C.; García-Vázquez, P.; Marcote, X.; Valenzuela, J. C., On the order of \((\{r, m \}; g)\)-cages of even girth, Discrete Math., 308, 2484-2491 (2008) · Zbl 1151.05024
[20] Araujo-Pardo, G.; Balbuena, C.; Valenzuela, J. C., Constructions of bi-regular cages, Discrete Math., 309, 1409-1416 (2009) · Zbl 1229.05129
[21] Hanson, D.; Wang, P.; Jorgensen, L. K., On cages with given degree sets, Discrete Math., 101, 109-114 (1992) · Zbl 0769.05051
[22] Yuansheng, Yang; Liang, Weifa, The minimum number of vertices with girth 6 and degree set \(D = \{r, m \}\), Discrete Math., 269, 249-258 (2003) · Zbl 1024.05044
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.