Diameter and connectivity of (D; g)-cages

Abstract

A (D; g)-cage is a graph having degree set D, girth g, and the minimum possible number of vertices. When D={r} the corresponding ({r}; g)-cage is clearly r-regular, and is called an (r; g)-cage. In this work we establish some structural properties of (D; g)-cages, generalizing some known properties for (r; g)-cages. In particular we prove that the diameter of a ({r, r+1}; g)-cage is at most g and also we prove that ({r, m}; g)-cages are 2-connected.

Keywords:

• cage
• degree set
• girth
• connectivity
• diameter

2000 AMS Subject Classification :

• 05C40

Acknowledgements

The authors want to thank the anonymous referees for their comments and suggestions which have contributed to improve the presentation of the paper. The research is supported by the Ministerio de Educación y Ciencia, Spain, and the European Regional Development Fund (ERDF) under project MTM2008-06620-C03-02/MTM, and by Catalonian Government 1298 SGR2009.