GRAPHS OF PRESCRIBED GIRTH AND BI-DEGREE

We say that a bipartite graph Gamma(V-1 boolean OR V-2, E) has bi-degr ee r, s if every vertex from V-1 has degree r and every vertex from V- 2 has degree s. Gamma is called an (r, s, t)-graph if, additionally, t he girth of Gamma is 2t. For t > 3, very few examples of (r, s, t)-gra phs were previously known. In this paper we give a recursive construct ion of (r, s, t)-graphs for all r, s, t greater than or equal to 2, as well as an algebraic construction of such graphs for all r, s greater than or equal to r greater than or equal to 3. (C) 1995 Academic Pres s, Inc.