Camino Balbuena
email: m.camino.balbuena@upc.edu

Xavier Marcote

Diego González-Moreno

Some properties of semiregular cages

Keywords: cage, degree set, girth, connectivity

A graph with degree set {r, r + 1} is said to be semiregular. A semiregular cage is a semiregular graph with given girth g and the least possible order. First, an upper bound on the diameter of semiregular graphs with girth g and order close enough to the minimum possible value is given in this work. As a consequence, these graphs are proved to be maximally connected when the girth g ≥ 7 is odd. Moreover an upper bound for the order of semiregular cages is given and, as an application, every semiregular cage with degree set {r, r + 1} is proved to be maximally connected for g ∈ {6, 8}, and when g = 12 for r ≥ 7 and r = 20. Finally it is also shown that every ({r, r + 1}; g)-cage is 3-connected.

Introduction

Throughout this work only undirected simple graphs without loops or multiple edges are considered. Unless stated otherwise, we follow [START_REF] Chartrand | Graphs and digraphs[END_REF] for terminology and definitions not explicitly given here.

Let G be a graph with set of vertices V (G) and set of edges E(G). Given a proper subset X of V (G), let [X, V (G) \ X] denote the set of edges with one end in X and the other in V (G) \ X. We denote by N (v) the neighborhood of a vertex v, the degree of a vertex v is |N (v)| = d(v), and the minimum degree of G is denoted by δ(G). The edge degree of uv ∈ E(G) is equal to d(u) + d(v) -2, and ξ(G) stands for the minimum edge degree of G. The distance d(u, v) between two vertices u and v is the length of a shortest path between them. The eccentricity of a vertex u is the largest distance between u and any other vertex of the graph. The diameter of G is denoted by diam(G) and is the maximum of the eccentricities of the vertices of the graph. The connectivity and edge connectivity of G, denoted respectively by κ(G), λ(G), are linked by the Whitney inequality κ(G) ≤ λ(G) ≤ δ(G). A graph G is maximally connected if κ(G) = δ(G), and maximally edge connected if λ(G) = δ(G). A restricted edge cut of a graph G is a set of edges whose deletion yields a nonconnected graph without isolated vertices. A graph G is said to be optimally restricted edge connected if the minimum cardinality of a restricted edge cut is equal to ξ(G), the minimum edge degree of G.

The degree set D of a graph G is the set of distinct degrees of the vertices of G. A (D; g)-graph is a graph with degree set D and girth g. The frequency of each degree in D is the number of vertices of the graph having this degree. A (D; g)-cage is a (D; g)-graph with the least possible order. A biregular cage is a (D; g)-cage with degree set D = {r, m}, m > r. A semiregular cage is a biregular cage with degree set D = {r, r + 1}.

The concept of (D; g)-cages was proposed by Chartrand, Gould, and Kapoor [START_REF] Chartrand | Graphs with prescribed degree set and girth[END_REF]. If D = {r}, (D; g)cages coincide with (r; g)-cages, which have been intensely studied since their introduction by Tutte [START_REF] Tutte | A family of cubical graphs[END_REF]. See the survey by Wong [START_REF] Wong | Cages -A Survey[END_REF] or the book by Holton and Sheehan [START_REF] Holton | The Petersen graph, Chapter 6: Cages[END_REF] or the recent survey by Exoo and Jajcay [START_REF] Exoo | Dynamic cage survey[END_REF]. The existence of (r; g)-cages was proved by Erdős and Sachs in the early 1960s [START_REF] Erdős | Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl[END_REF], and using this result Chartrand, Gould and Kapoor [START_REF] Chartrand | Graphs with prescribed degree set and girth[END_REF] proved the existence of (D; g)-cages.

Construction of (D; g)-cages is a challenging topic as well as a very difficult task. This goal has only been achieved for a few pairs (D; g), and most of them correspond to the case D = {r}. Even the problem of determining the value of the order of a (D; g)-cage, denoted by n(D; g), is a difficult one and is open for most of degree sets D and girths g. A natural approach is to try to estimate upper and lower bounds as close as possible for n(D; g) (written n(r; g) instead of n({r}; g) when D = {r}).

For the case of (r; g)-cages, Lazebnik, Ustimenko and Woldar [START_REF] Lazebnik | New upper bounds on the order of cages[END_REF], improving a previous result of Sauer [START_REF] Sauer | Extremaleigenschaften regulärer Graphen gegebener Taillenweite, I and II, Sitzungsberichte Österreich[END_REF], obtained the following upper bound for n(r; g): Theorem 1.1 [START_REF] Lazebnik | New upper bounds on the order of cages[END_REF] Let r ≥ 2 and g ≥ 5 be integers, and let q denote the smallest odd prime power verifying r ≤ q. Then n(r; g) ≤ 2rq

3g 4 -a , (1)
where a = 4, 11 4 , 7 2 , 13 4 for g ≡ 0, 1, 2, 3 (mod 4) respectively. Recently, the above result has been improved for g = 6, 8, 12 in several references listed in the following theorem. Theorem 1.2 Let q ≥ 2 be a prime power and g = 6, 8, 12.

(i) [START_REF] Abreu | On (minimal) regular graphs of girth 6[END_REF][START_REF] Balbuena | Incidence matrices of projective planes and other bipartite graphs of few vertices[END_REF] n(q; 6) ≤ 2(q 2 -1);

(ii) [START_REF] Balbuena | Incidence matrices of projective planes and other bipartite graphs of few vertices[END_REF] n(q -1; 6) ≤ 2(q 2q -2);

(iii) [START_REF] Araujo-Pardo | Constructions of small regular graphs of girth 6[END_REF] n(k; 6) ≤ 2(qk -2) for all k ≤ q -1;

(iv) [START_REF] Balbuena | A construction of small regular graphs of girth 8[END_REF] n(k; 8) ≤ 2q(qk -1) for all k ≤ q;

(v) [START_REF] Gács | On geometric constructions of (k, g)-graphs[END_REF] n(q; 8) ≤ 2q(q 2 -2) if q is a square; (vi) [START_REF] Araujo-Pardo | Finding small regular graphs of girth 6, 8 and 12 as subgraphs of cages[END_REF] n(k; 12) ≤ 2kq 2 (q 2 -1) for all k ≤ q.

As far as the lower bounding of n(D; g) is concerned, Downs, Gould, Mitchem and Saba [START_REF] Downs | D; n)-cages[END_REF] obtained the following bound, by counting the vertices emerging from a vertex with maximum degree. Theorem 1.3 [START_REF] Downs | D; n)-cages[END_REF]

Let D = {a 1 , a 2 , . . . , a k } be a set of positive integers with 2 ≤ a 1 < a 2 < • • • < a k , and g ≥ 3. Then n(D; g) ≥ n 0 (D; g) =        1 + t i=1 a k (a 1 -1) i-1 if g = 2t + 1, 1 + t-1 i=1 a k (a 1 -1) i-1 + (a 1 -1) t-1 if g = 2t.
(

) 2
Expression ( 2) is easily seen to hold when D = {r} by replacing both a k and a 1 with r. A (D; g)-cage satisfying n(D; g) = n 0 (D; g) is called a minimal (D; g)-cage. Kapoor, Polimeni and Wall [START_REF] Kapoor | Degree sets for graphs[END_REF] proved that (D; 3)-cages are minimal, i.e., n(D; 3) = n 0 (D; 3) = 1 + a k .

Chartrand, Gould and Kapoor [START_REF] Chartrand | Graphs with prescribed degree set and girth[END_REF] proved that ({2, m}; g)-cages are minimal. They also proved that n({r, m}; 4) = n 0 ({r, m}; 4) = r + m for any r ≥ 2. Moreover, Downs, Gould, Mitchem and Saba [START_REF] Downs | D; n)-cages[END_REF] proved that n({3, m}; 5) = n 0 ({3, m}; 5) = 1 + 3m and n({3, m}; 7) = n 0 ({3, m}; 7) = 1 + 7m, for m ≥ 4; and n({3, m}; 9) = n 0 ({3, m}; 9) = 1 + 15m, for m ≥ 6. Araujo, Balbuena, and Valenzuela [START_REF] Araujo-Pardo | Constructions of bi-regular cages[END_REF] provided some constructions of ({r, m}; g)-cages in the case g ∈ {5, 7, 11}, when r -1 is a prime power, k an even integer and m = k(r -1).

Yuansheng and Liang [START_REF] Yuansheng | The minimum number of vertices with girth 6 and degree set D = {r, m}[END_REF] proved that n({r, m}; 6) ≥ 2(rmm + 1), and they conjectured that n({r, m}; 6) = 2(rmm + 1). Moreover, they proved that the conjecture is true when m -1 is a prime power and also for any m and r = 3, 4, 5. Constructions of minimal ({r, m}; 6)-cages when r -1 is a prime power and m = k(r -1) + 1 for k ≥ 2 are also provided [START_REF] Araujo | On the order of ({r, m}, g)-cages of even girth[END_REF]. For the case where the girth is even and greater than 6, no new results have been achieved.

In the Table 1 we present some of the known exact values of n({r, m}; g).

n({r, m}; g) g = 5 g = 6 g = 7 g = 8 g=9 g = 11

r = 3 3m + 1 4m + 2 7m + 1 8m + m 3 + 5 1 + 15m m ≥ 4 m ≥ 4 m ≥ 4 m = 3k m ≥ 6 [14] [30] [14] [5] [14] r = 4 4m + 1 6m + 2 m ≥ 5 m ≥ 5 [19] [19] 5 ≤ r < m 2(rm -m + 1) m -1 = p α [4, 30] 3 ≤ r < m 1 + rm 2(rm -m + 1) 1 + m(r 2 -r + 1) 1 + m (r-1) 5 -1 r-2 r -1 = p α m = k(r -1) m = k(r -1) + 1 m = k(r -1) m = k(r -1) k ≥ 2 even k ≥ 2 [4], or k ≥ 2 even k ≥ 2 even [5] m = kr, k ≥ 2 [5] [5] [5]
Tab. 1: Exact values of n({r, m}; g) ( p α denotes a prime power).

Concerning other structural properties of interest of (D; g)-cages, some results for (r; g)-cages have been extended by Balbuena and Marcote [START_REF] Balbuena | Diameter and connectivity of (D; g)-cages[END_REF][START_REF] Balbuena | Monotonicity of the order of (D; g)-cages[END_REF].

Theorem 1.4 [START_REF] Balbuena | Monotonicity of the order of (D; g)-cages[END_REF] Let D = {a 1 , a 2 , . . . , a k } with 2 ≤ a 1 < a 2 < • • • < a k , and let g 1 , g 2 be two integers such that 3 ≤ g 1 < g 2 . Then n(D; g 1 ) < n(D; g 2 ) provided that any of the following conditions hold:

(i) g 1 = 3;
(ii) some a i ∈ D is even and has frequency at least two;

(iii) every a i ∈ D is even; (iv) some a i ∈ D is odd and g 1 ≥ k -1; (v) k ≤ 5; (vi) some a i ∈ D is odd for i ≥ ⌊(k + 8)/3⌋
and has frequency at least 3. Theorem 1.5 [START_REF] Balbuena | Diameter and connectivity of (D; g)-cages[END_REF] Let D = {r, m} with 2 ≤ r < m, and let G be a (D; g)-cage. Then the diameter of G is at most g if one of the following assertions hold:

(i) r is even and the frequency of r is at least two;

(ii) m = r + 1.
Apart from the order and the diameter, also the connectivity of (D; g)-cages is a basic goal to approach. In the following theorem we list some useful known sufficient conditions on the diameter of a graph in terms of the girth to guarantee optimal results for some parameters accounting for its connectivity.

Theorem 1.6

Let G be a graph with minimum degree δ ≥ 2, diameter diam(G) and girth g. Then, (i) [START_REF] Soneoka | Sufficient conditions for maximally connected dense graphs[END_REF]

if diam(G) ≤ 2⌊(g -1)/2⌋ -1, then κ(G) = δ; (ii) [27] if diam(G) ≤ 2⌊(g -1)/2⌋, then λ(G) = δ; (iii) [8] if diam(G) ≤ g -2, then G is optimally restricted edge connected.
Going back to the framework of (D; g)-cages, the connectivity of semiregular cages was studied by Balbuena et al. [START_REF] Balbuena | On the connectivity of semiregular cages[END_REF]. They proved the following result.

Theorem 1.7 [START_REF] Balbuena | On the connectivity of semiregular cages[END_REF] Every ({r, r + 1}; g)-cage is maximally edge connected. And every ({3, 4}; g)-cage is maximally connected. This paper is devoted to semiregular cages, and is organized as follows. In Section 2 we prove that the diameter of an ({r, r + 1}; g)-graph whose order is close enough to the (minimal) bound n 0 ({r, r + 1}; g) has diameter at most g -2. As an application every ({r, r + 1}; g)-graph with odd girth and order close enough to n 0 ({r, r + 1}; g) is shown to be maximally connected. In Section 3 we present an upper bound on the order of a semiregular cage. Finally, Section 4 deals with the connectivity of semiregular cages. With the help of the aforementioned new upper bound on n({r, r + 1}; g), semiregular cages are proved to be maximally connected when g = 6, 8, and when g = 12 for r ≥ 7 and r = 20. Furthermore, it is also shown that every ({r, r + 1}; g)-cage with r ≥ 4 and g ≥ 6 is 3-connected, extending a previous result obtained by the authors in [START_REF] Balbuena | On the connectivity of semiregular cages[END_REF] for r = 3.

Diameter of ({r, r + 1}; g)-graphs with small order

In what follows an upper bound on the diameter of semiregular graphs with small order is given.

Theorem 2.1 Let G be an ({r, r + 1}; g)-graph with r ≥ 2 and g ≥ 6 on at most n 0 ({r, r + 1}; g) + r -1 vertices. Then the diameter is at most diam(G) ≤ g -2.

Proof: Let us first prove the following claim.

Claim: No two vertices of degree r + 1 are adjacent. Suppose that there exists an edge

xy ∈ E(G) such that d(x) = d(y) = r + 1, then if g is odd it follows |V (G)| ≥ 1 + (r + 1) (g-3)/2 i=0 (r -1) i + (g-5)/2 i=0 (r -1) i = n 0 ({r, r + 1}; g) + (g-5)/2 i=0 (r -1) i
which is a contradiction to the hypothesis. And if g is even then

|V (G)| ≥ 2 + 2r g/2-2 i=0 (r -1) i = 1 + r g/2-2 i=0 (r -1) i + (r -1) g/2-1 + 2 g/2-2 i=0 (r -1) i = n 0 ({r, r + 1}; g) + g/2-2 i=0 (r -1) i
which is again a contradiction to the hypothesis. Then any two vertices of degree r + 1 are at distance at least two. 2 To continue the proof, first suppose that G contains two vertices u and v of degree r such that d(u, v) ≥ g -1. Let us consider the graph G ′ = G ∪ {uv}. If G ′ contains a vertex of degree r, then G ′ is an ({r, r + 1}; g)-graph having two vertices of degree r + 1 at distance one, contradicting the Claim. If there are no vertices of degree r in G ′ , then G ′ is an (r + 1; g)-graph and

|V (G ′ )| = |V (G)| ≥ n(r + 1; g) > n 0 ({r, r + 1}; g) + r -1.
Therefore d(u, v) ≤ g -2 for all two vertices u, v of degree r. Next let us see that any vertex u of degree r + 1 has eccentricity at most ⌈(g + 1)/2⌉.

Let us consider the subgraph H induced by the sets of vertices

(g-1)/2 i=0 N i (u), if g is odd, g/2-1 i=0 N i (e), if g is even,
e being an edge incident with u. Then

|V (H)| ≥            1 + (r + 1) (g-1)/2 i=1 (r -1) i-1 = n 0 ({r, r + 1}; g), if g is odd, 2 g/2-1 i=0 (r -1) i + g/2-2 i=0
(r -1) i = n 0 ({r, r + 1}; g), if g is even.

Clearly if |V (G)| = |V (H)|, then G = H and so for all x ∈ V (G), d(u, x) ≤ (g -1)/2 when g is odd, and d(u, x) ≤ g/2 for g even; hence the theorem is valid. Thus assume that

|V (G)| > |V (H)| and let R = V (G) \ V (H). If some vertex s ∈ R is not joined to some vertex in H, then |V (R)| ≥ d(s) + 1 ≥ r + 1, which means that |V (G)| ≥ |V (H)| + |R| ≥ n 0 ({r, r + 1}; g) + r + 1
, a contradiction to the hypothesis. Therefore, any vertex of R is joined to some vertex of H yielding for all x ∈ V (G):

d(u, x) ≤ (g + 1)/2, for g odd, g/2 + 1, for g even,
hence the claimed eccentricity of u holds. Therefore the diameter of G is at most g -2.

2

The next result follows combining Theorem 1.6 and Theorem 2.1.

Theorem 2.2

Let G be an ({r, r + 1}; g)-graph with r ≥ 2. Then G is maximally connected if g ≥ 7 is odd and the order is at most n 0 ({r, r + 1}; g) + r -1.

In [START_REF] Balbuena | Diameter and connectivity of (D; g)-cages[END_REF] was proved that all minimal ({r, m}; g)-cages are 2-connected. Hence Theorem 2.2 is an improvement of this result when m = r + 1 and the order is close enough to the minimal bound.

3 Upper bounds on the order of ({r, r + 1}; g)-cages

Note that n({r, r + 1}; g) < n(r + 1; g) for every g ≥ 4. Indeed, if G is an (r + 1; g)-cage with g ≥ 4, then for every v ∈ V (G) the graph Gv is an ({r, r + 1}; g ′ )-graph with g ′ ≥ g, hence n({r, r + 1}; g) ≤ n({r, r + 1}; g ′ ) ≤ |V (G)| -1 < n(r + 1; g), the first inequality due to Theorem 1.4. Next an upper bound for n({r, r + 1}; g) is given. Theorem 3.1 Let r ≥ 2 and g ≥ 6 be two integers. Then

n({r, r + 1}; g) ≤ n(r + 1; g) - (r+1)r (g-3)/2 -2 r-1 if g is odd, 2r (g-2)/2 -2 r-1
if g is even and n(r + 1; g) > n 0 (r + 1; g).

Moreover if g is even and n(r + 1; g) = n 0 (r + 1; g), then n({r, r + 1}; 6) = 2r 2 and n({r, r + 1}; g) ≤ 1 + 2r (g-6)/2 (r 2 -1) for g = 8, 12.

Proof: Let G be an (r + 1; g)-cage. Let us distinguish two cases.

Case 1. g ≥ 7 odd. In this case note that G is not a minimal cage, since minimal cages for g odd only exist when r + 1 = 2 (cycles), g = 3 (complete graphs), and g = 5 and r + 1 = 3, 7 (and possibly) 57; see [START_REF] Hoffman | On Moore graphs with diameters 2 and 3[END_REF]. This means that the diameter is diam(G) ≥ (g + 1)/2. Let u ∈ V (G) be a vertex of maximum eccentricity, and let us consider the following sets of neighbors:

N i (u) = {z ∈ V (G) : d(u, z) = i}, i = 0, 1, . . . , diam(G).
Note that N 0 (u) = {u} and N 1 (u) = N (u). Now consider the induced subgraph T spanned by the vertices within distance µ ≤ (g -3)/2 from u. Since G has girth g, it is clear that T is a tree.

Observe that d T (z) = r + 1 for all z ∈ N i (u) with i ≤ (g -5)/2, d T (z) = 1 for all z ∈ N (g-3)/2 (u), and the order of T is

|V (T )| = g-3 2 i=0 |N i (u)| = 1 + (r + 1) g-5 2 i=0 r i = (r + 1)r (g-3)/2 -2 r -1 .
Let G * = G -V (T ). Notice that both N (g-1)/2 (u) and N (g+1)/2 (u) are proper subsets of

V (G * ). Furthermore d G * (z) = r if z ∈ N i (u) with i = (g -1)/2 and d G * (z) = r + 1 if z ∈ N i (u) with i > (g -1)/2.
Then G * is an ({r, r + 1}; g * )-graph with g * ≥ g and from Theorem 1.4 it follows n({r, r + 1}; g) ≤ n({r, r

+ 1}; g * ) ≤ |V (G * )| = |V (G)| -|V (T )| = n(r + 1; g) - (r + 1)r (g-3)/2 -2 r -1 .
Case 2. g ≥ 6 even. Let e = uv ∈ E(G) and

N i (e) = {z ∈ V (G) : d({u, v}, z) = i}, i = 0, 1, . . . , l, with l ≥ g 2 -1.
Consider the subgraph T induced by the vertices within distance µ ≤ (g -4)/2 from e. Since G has girth g, then T is a tree. Notice that d T (z) = r + 1 for all z ∈ N i (e) with i ≤ (g -6)/2 and d T (z) = 1 for all z ∈ N (g-4)/2 (e). The order of T is

|V (T )| = 2(1 + r + r 2 + . . . + r (g-4)/2 ) = 2 g-4 2 i=0 r i = 2r (g-2)/2 -2 r -1 .
We need to distinguish two subcases. Subcase 2.1: Suppose that G is not a minimal cage of even girth, hence n(r + 1; g) > n 0 (r + 1; g).

Let G * = G -V (T ). Note that in this case N (g-2)/2 (e) and N g/2 (e) are proper subsets of

G * . Furthermore, d G * (z) = r if z ∈ N (g-2)/2 (e) and d G * (z) = r + 1 if z ∈ N i (e) for i > (g -2)/2.
Hence G * is an ({r, r + 1}, g * )-graph with girth g * ≥ g and from Theorem 1.4 it follows n({r, r + 1}; g) ≤ n({r, r

+ 1}; g * ) ≤ |V (G * )| = |V (G)| -|V (T )| = n(r + 1; g) - 2r (g-2)/2 -2 r -1 .
Subcase 2.2: Suppose that G is a minimal cage of even girth. Note that in this case diam(G) = g/2 with g = 6, 8, 12 and n(r + 1; g) = n 0 (r + 1; g). If g = 6, G is the incidence graph of a projective plane = (P, L) of order r, then all the lines L ∈ L have r + 1 points and every point p ∈ P is incident with r + 1 lines. Let L p be the set of lines incident with the point p, and let A be a line such that p / ∈ A. Let B ∈ L p and denote by q the point {q} = A ∩ B. Let us remove from the projective plane the point p and all the lines of the set L p -B, and also remove the line A and all its points except the point q. Denote by * the obtained incidence structure, i.e., * = (P \ ({p} ∪ (Aq)), L \ ((L p -B) ∪ {A})). Hence * has r 2 + r + 1 -(r + 1) = r 2 points and r 2 + r + 1 -(r + 1) = r 2 lines.

Observe that * has exactly r -1 lines of cardinality r + 1, which are all the lines through point q except line B, which has cardinality r because B has lost the point p. The rest of the lines have cardinality r since they have lost the point that shared with A (different from q). Moreover, * has exactly r -1 points incident with r + 1 lines, which are all the points of B different from q. Each of the remaining points p ′ is incident with r lines because it has lost the line through point p and p ′ . Therefore the incidence graph corresponding to * is an ({r, r+1}; 6)-graph with 2r 2 vertices. Taking into account the lower bound n({r, r + 1}; 6) ≥ 2r 2 proved by Yuansheng and Liang [START_REF] Yuansheng | The minimum number of vertices with girth 6 and degree set D = {r, m}[END_REF] we get that n({r, r + 1}; 6) = 2r 2 . For g = 8, 12, we proceed as in the paper [START_REF] Araujo-Pardo | Finding small regular graphs of girth 6, 8 and 12 as subgraphs of cages[END_REF]. Let T uv be the induced subgraph spanned by the vertices within distance µ ≤ (g -6)/2 from the edge e = uv. Let be the following subset of vertices

u 1 ∈ N (u) -v and v 1 ∈ N (v) -u. Let H u1v1 z * u 1 v 1 u v
H u1v1 = g-2 2 j= g-4 2 N j (e) ∩ (N j-1 (u 1 ) ∪ N j-1 (v 1 )).
Let z * ∈ N (g-6)/2 (e) -(N (g-8)/2 (u 1 ) ∪ N (g-8)/2 (v 1 )), which can be chosen because r

+ 1 ≥ 3. Let G * = G -(V (T uv ) -z * ) -V (H u1v1 ), see Figure 1. Note that d G * (z * ) = r and d G * (z i ) = r + 1 for every z i ∈ N G * (z * ).
Every other vertex of G * has degree r, since each remaining vertex v ∈ N (g-4)/2 (e) has lost exactly one neighbor in T uv , and each vertex w ∈ N (g-2)/2 (e) has lost exactly one neighbor belonging to either N (g-4)/2 (u 1 ) or N (g-4)/2 (v 1 ). Hence G * is an ({r, r + 1}; g * )-graph with girth g * ≥ g. Moreover, the order of G * is:

|V (G * )| = n 0 (r + 1; g) -2 r (g-4)/2 -1 r -1 -1 -2(r (g-6)/2 + r (g-4)/2 ) = 2r (g-2)/2 -2r (g-6)/2 + 1 = 2r (g-6)/2 (r 2 -1) + 1.
In either case the theorem is valid. 2

In [START_REF] Araujo | On the order of ({r, m}, g)-cages of even girth[END_REF][START_REF] Yuansheng | The minimum number of vertices with girth 6 and degree set D = {r, m}[END_REF] was obtained that n({r, m}; 6) = 2(rmm + 1) for all m > r ≥ 3 with m -1 a prime power. When m = r + 1 we have n({r, r + 1}; 6) = 2r 2 . In the above Theorem 3.1, this result has been extended for every r for which there exists a projective plane.

Observe that r ≥ 6. First suppose that r + 1 = q where q ≥ 7 is a prime power. Both Theorem 3.1 and Theorem 1.2 yield n({q -1, q}; g) ≤ n(q; g) -2

(q -1)

(g-2)/2 -1 q -2 ≤ 2q (g-6)/2 (q 2 -1) -2 (q -1) (g-2)/2 -1 q -2 =    2q 2 -2q -2 if g = 6 2q 3 -2q 2 -2 if g = 8 2q 5 -2q 4 + 4q 3 -8q 2 + 4q -2 if g = 12.
Now, it is easy to verify that n({q -1, q}; g) ≤ N (q -1, g, q -1) if q ≥ 7 for g = 6, 8, and if q ≥ 13 when g = 12.

Second, suppose that r + 1 = q -1 where q is a prime power; hence r ≥ 14 and q ≥ 16 can be assumed. Again from Theorem 3.1 and Theorem 1.2 it follows

n({q -2, q -1}; g) ≤    2q 2 -4q -2 if g = 6; 2q 3 -4q 2 + 4q -6 if g = 8; 2q 5 -4q 4 + 12q 3 -36q 2 + 46q -22 if g = 12.
Now, it is easy to verify that n({q -2, q -1}; g) ≤ N (q -2, g, q -2) if q ≥ 16 for g = 6, 8, and if q ≥ 23 for g = 12.

Case (c): Suppose n(r + 1; g) > n 0 (r + 1; g), with r + 1 ≤ q -2, where q denotes a prime power, and g = 6, 8, 12.

Note that we may assume that r + 1 ∈ {q ′ -1, q ′ , q ′ + 1} for every prime power q ′ , (otherwise Cases 2⌊ 7 6 (r + 1)⌋(⌊ 7 6 (r + 1)⌋(r + 1) -1) -2(r 2 + r + 1) if g = 8.

2⌊ 7 6 (r + 1)⌋ 2 (⌊ 7 6 (r + 1)⌋ 2 -1)(r + 1) -2(r 4 + r 3 + r 2 + r + 1) if g = 12.

As in the above cases, it is very easy to verify that n({r, r + 1}; g) ≤ N (r, g, r) for g = 6, 8; and for g = 12 if r = 20.

As a consequence of the above three cases, the result is valid. 2

Semiregular cages are 3-connected

In this section we prove that most of ({r, r + 1}; g)-cages are 3-connected.

Theorem 4.4 Every ({r, r + 1}; g)-cage with r ≥ 3 and g ≥ 6 is 3-connected.

y 3 y 2 x 2 = y 1 x 1 y ′ 3 y ′ 2 x ′ 2 = y ′ 1 x ′ 1 H H ′ E ′

Proof:

The results holds for r = 3 by [START_REF] Balbuena | On the connectivity of semiregular cages[END_REF], hence asssume r ≥ 4 for the rest of the proof. Let G be an ({r, r + 1}; g)-cage satisfying the hypothesis. We can suppose that G is 2-connected following [START_REF] Balbuena | On the connectivity of semiregular cages[END_REF]. Let S = {x, y} be a cutset of G that minimizes the order of the smallest component of the graph obtained by deleting from G a 2-cutset. Let H be a smallest component of G -S, notice that

|N (x) ∩ V (H)| ≥ 2 and |N (y) ∩ V (H)| ≥ 2, otherwise if N (x) ∩ V (H) =
{z} the set {z, y} would be a cut set that leaves a component with fewer vertices than H contradicting the choice of S, and the same occurs if |N (y) ∩ V (H)| = 1. Furthermore, since g ≥ 6 it follows that |N (x) ∩ N (y)| ≤ 1. Let us denote N (x) ∩ V (H) = {x 1 , x 2 , . . . , x α } and N (y) ∩ V (H) = {y 1 , y 2 , . . . , y β }, and suppose α ≤ β without loss of generality. Let H ′ be a copy of H with V (H) ∩ V (H ′ ) = ∅, and for every v ∈ V (H) let v ′ denote its copy in H ′ . Let G * be a new graph obtained from the union of H and H ′ and by adding the following edges:

E ′ = {x 1 x ′ 1 , x 2 x ′ 2 , . . . , x α x ′ α , y 1 y ′ 2 , y 2 y ′ 3 , . . . , y β y ′ 1 }.
Observe that if N (x) ∩ N (y) ∩ V (H) = {z}, then the vertices z and z ′ are both incident with two new added edges (see Figure 2). Hence, each vertex in G * has the same degree it had in G and

|V (G * )| = 2|V (H)| ≤ |V (G)| -2. Now, let us show that g(G * ) = g * ≥ g. Let C be a cycle of G * . Since E ′ is an edge cut of G * then |E(C) ∩ E ′ | is an even number. (a) If |E(C) ∩ E ′ | = 0, then C corresponds with a cycle of G, therefore C has length at least g. (b) Suppose |E(C) ∩ E ′ | = 2. If x i x ′
i and x j x ′ j are in E(C) for some distinct i, j, then the length l(C) of C is:

l(C) ≥ d H (x i , x j ) + d H ′ (x ′ i , x ′ j ) + 2 = 2d H (x i , x j ) + 2 ≥ 2(g -2) + 2 = 2g -2 > g.
And the same occurs if y i y ′ i+1 and y j y ′ j+1 are in E(C) for some different i, j. Finally, if x i x ′ i and y j y ′ j+1 are in E(C), then

l(C) ≥ d H (x i , y j ) + d H ′ (x ′ i , y ′ j+1 ) + 2 = d H (x i , y j ) + d H (x i , y j+1 ) + 2 ≥ d H (y j , y j+1 ) + 2 ≥ (g -2) + 2 = g. (c) Suppose |E(C) ∩ E ′ | ≥ 4.
If C contains an (x i , x j )-path or an (y s , y t )-path, then analogously to (b), l(C) ≥ (g -2) + 4 > g.

The unique remaining case to consider is when C contains neither an (x i , x j )-path nor an (y s , y t )path. Let us consider an (x i , y j )-path in H and an (x ′ s , y ′ t )-path in H ′ . Observe that we can assume that at most one of the conditions i = s, j = t holds; otherwise we consider other (x ′ h , y ′ p )-path in H ′ instead of the path (x ′ s , y ′ t ), as s = h and t = p. When i = s (j = t) we have

l(C) > d H (x i , y j ) + d H ′ (x ′ i , y ′ t ) + 4 = d H (x i , y j ) + d H (x i , y t ) + 4 ≥ d H (y j , y t ) + 4 ≥ (g -2) + 4 > g.
Analogously in case j = t (i = s). When i = s and j = t, since the union of an (x i , y j )-path, an (x s , y t )-path and the edges x i x, xx s , y j y, yy t contains a cycle that corresponds with a cycle in G, it follows that l(C) ≥ (g -4) + 4 = g.

We have already seen that g(G * ) = g * ≥ g stands for the girth of G * . Next we consider the degree set of G * . If G * contains some vertex with degree r and some vertex with degree r + 1, then G * is an ({r, r + 1}; g * )-graph with fewer vertices than G, contradicting Theorem 1.4. Hence the graph G * may be assumed to be a regular graph. If G * is an (r + 1; g * )-graph, then the graph G *v where v ∈ V (G * ) is an ({r, r + 1}; g * )-graph with fewer vertices than G, yielding a contradiction to Theorem 1.4. Hence G * is an (r; g * )-graph. Let us show that G * has diam(G * ) ≥ g -1. We distinguish three cases. Case 1. N (x) ∩ N (y) ∩ V (H) = ∅, α ≥ 2 and β ≥ 3.

Since g > 4 then N (x) ∩ N (y) ∩ V (H) = {x α } = {y β } may be assumed. Note that d H (x i , y j ) ≥ g -4, for every x i = y j since, when i = α and j = β, an (x i , y j )-path in H joint with the edges x i x, xx α , x α y, yy j of G contains a cycle in G of length at least g; and when i = α or j = β, d H (x i , x j ) ≥ g -2.

Then (for some y k = y 1 ): dG * (y1, y ′ 1 ) = min{dH (y1, xj) + 1 + d H ′ (x ′ j , y ′ 1 ), dH(y1, y k ) + 1 + d H ′ (y ′ k+1 , y ′ 1 ), 1 + d H ′ (y ′ 2 , y ′ 1 )} ≥ min{2(g -4) + 1, 2(g -2) + 1, 1 + g -2} = g -1, since g ≥ 6, 2(g -4) + 1 ≥ g -1.

diam(G * ) ≥ g -1 if g is even, g if g is odd.
The same occurs if λ(G * ) < r = 4. If r = 4 = λ(G * ), since the set E ′ is a restricted edge cut because g > 4, then Theorem 1.6(iii) implies diam(G * ) ≥ g -1 as the minimum edge degree of G * is equal to 2(r -1) = 6.

Therefore G * contains two vertices z 1 and z 2 such that d G * (z 1 , z 2 ) ≥ g -1. By joining the edge z 1 z 2 to G * , the graph G * ∪ {z 1 z 2 } is an ({r, r + 1}; g * )-graph with fewer vertices than G and g * ≥ g, yielding a contradiction. 2

Fig. 1 :

 1 Fig. 1: The deleted vertices in the (4, 8)-cage are shown in the box. The resulting graph is a ({3, 4}; 8)-graph on 49 vertices.

1 2ln 2

 12 (a) or (b) hold). Then r + 1 ≥ 21 and hence 1 + (r+1) ≤ 7 6 , thus by Theorem 4.2 we may assume that q ≤ ⌊ 7 6 (r + 1)⌋. Again from Theorem 3.1 and Theorem 1.2 it follows that n({r, r+1}; g) + 1)⌋(r + 1) -4 -2(r + 1) if g = 6;

Fig. 2 :

 2 Fig. 2: Construction of G * .

Case 2 .

 2 N (x) ∩ N (y) ∩ V (H) = ∅, α ≥ 2 and β ≥ 3.Then (for some y k ∈ {y 1 , y 3 }):d G * (y 3 , y ′ 2 ) = min{d H (y 3 , y 1 ) + 1, d H (y 3 , x i ) + 1 + d H ′ (x ′ i , y ′ 2 ), d H (y 3 , y k ) + 1 + d H ′ (y ′ k+1 , y ′ 2 )} ≥ min{g -2 + 1, d H (y 3 , y 2 ) + 1, 2(g -2) + 1} = g -1.Case 3. α = β = 2. Hence λ(G * ) ≤ |E ′ | = 4. If r ≥ 5 then λ(G * ) < r and by Theorem 1.6(ii),

Acknowledgments

This research was 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. We would like to thank the anonymous referees for their suggestions and comments.

Vertex connectivity

Every ({r, r + 1}; g)-cage with r ≥ 2 has been shown to be 2-connected [START_REF] Balbuena | On the connectivity of semiregular cages[END_REF]. The main objective of this section is to contribute to answer this question by further approaching the connectedness of semiregular cages. To do that we will use the following known result. Theorem 4.1 [START_REF] Marcote | On the connectivity of cages with girth five, six and eight[END_REF] Let G be a connected graph with minimum degree δ ≥ 3, girth g, and order n. Let k be an integer such that

We also use the following result due to Dusart [START_REF] Dusart | The k th Prime is Greater Than k(lnk + lnlnk -1) for k ≥ 2[END_REF] on the existence of prime powers in short intervals of integers. Theorem 4.2 [START_REF] Dusart | The k th Prime is Greater Than k(lnk + lnlnk -1) for k ≥ 2[END_REF] Let r be a positive integer.

] contains a prime number.

(ii) If 6 ≤ r ≤ 3276 then the interval [r, 7r 6 ] contains a prime power.

Using Theorem 4.1 and Theorem 4.2 we obtain the next theorem.

Theorem 4.3

Let G be an ({r, r + 1}; g)-cage with r ≥ 3 and g ≥ 6. Then G is maximally connected provided that any of the following conditions hold.

(i) g = 6, 8.

(ii) g = 12 and r ≥ 7, r = 20.

Proof: By Theorem 4.1, it is enough to show that |V (G)| ≤ N (r, g, r). Let us distinguish the following cases.

Case (a): Suppose that n(r + 1; g) = n 0 (r + 1; g).

Then g = 6, 8, 12. For every r ≥ 3 if g = 6, 8, and for every r ≥ 7 if g = 12 it follows from Theorem 3.1 that:

Then the result follows from Theorem 4.1. Note that case (a) holds if r is a prime power.

Case (b): Suppose n(r + 1; g) > n 0 (r + 1; g) with r ∈ {q -1, q -2}, where q denotes a prime power, and g = 6, 8, 12.