\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{}{}{}

\usepackage{amsmath,amsthm,amsfonts,amssymb,enumitem}
\usepackage{url}
\usepackage{tikz}
%\usepackage{geometry}
%\geometry{textwidth=145mm, textheight=250mm}
\usepackage{graphicx}


%\input amssym.tex

%\def\vf{\varphi}
%\def\proof{\par\noindent{\it Proof.\ \ }}
%\def\qed{\ifmmode\square\else\nolinebreak\hfill
%$\square$\fi\par\vskip12pt}
%\def\rank{{\rm rank}} 
%\newcommand{\calC}{{\cal C}_{G}^b(n)} 
%\newcommand{\calW}{{\cal W}_{G}^b(n)} 

%\def\ov{\overline} \def\l{\langle} \def\r{\rangle} \def\tr{{\rm tr}}
%\def\div{\,\Big|\,} \def\ddiv{\,\Big\Vert\,}\def\notdiv{{\,\not\Big|\,}}

\def\ZZ{{\mathbb Z}}
%\def\FF{\Bbb F} \def\ZZ{\Bbb Z}

%\def\Aut{{\rm Aut}} \def\Inn{\rm Inn} \def\Out{\rm Out}
%\def\Cay{{\rm Cay}}
%\def\C{{\bf C}}\def\N{{\bf N}}\def\Z{{\bf Z}} \def\O{{\bf O}}

%\def\Ga{\Gamma}
%\def\a{\alpha} \def\b{\beta} \def\d{\delta}\def\g{\gamma} \def\s{\sigma}
%\def\t{\tau} \def\va{\varepsilon}

%\def\A{{\rm A}}\def\Sym{{\rm Sym}}

%\def\PSL{{\rm PSL}}
%\def\Fix{{\rm Fix}}
%\def\rst{\!\!\restriction}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%\makeatletter
%\renewcommand\section{\@startsection {section}{1}{\z@}%
%{-3.5ex \@plus -1ex \@minus -.2ex}%
%{2.3ex \@plus.2ex}%
%{\raggedright\normalfont\Large\bfseries}}
%\makeatother


\title{\bf Generalized cages \footnote{Dedicated to Branko Gr\"{u}nbaum whose work is a constant source of inspiration for us.}}
\author{ Marko Boben \thanks{Supported in part by the project P1-0294.} \\
\small University of Primorska, IAM,\\[-0.8ex]
\small Faculty of Computer Science, University of Ljubljana, \\ [-0.8ex]
\small and Institute of Mathematics, Physics, and Mechanics, Slovenia \\
\small\tt marko.boben@fri.uni-lj.si
\and
Robert Jajcay \thanks{Supported in part by the projects   
               VEGA 1/0577/14, VEGA 1/0474/15, NSFC 11371307, 
               and  Project: Mobility -  ITMS code: 26110230082.} \\
\small Faculty of Mathematics, Physics and Computer Science, \\ [-0.8ex]
\small Comenius University, Bratislava, Slovakia  \\
\small\tt robert.jajcay@fmph.uniba.sk 
\and
Toma\v z Pisanski \thanks{Supported in part by the projects P1-0294, J1-6720, N1-0011, and N1-0032.} \\
\small University of Primorska,\\[-0.8ex]
\small Faculty of Mathematics and Physics, University of Ljubljana,  \\ [-0.8ex]
\small and Institute of Mathematics, Physics, and Mechanics, Slovenia \\
%\small Jadranska 19, 1000 Ljubljana, Slovenia \\
\small\tt tomaz.pisanski@fmf.uni-lj.si}

\date{\dateline{Sep 12, 2014}{Mar 12, 2015}{2015}\\
\small Mathematics Subject Classifications: 05C07, 05C38, 05B30}

\begin{document}

\maketitle

\begin{abstract}
Let $2 \leq k_1 < k_2 < \cdots < k_t $, $3 \leq g_1 < g_2 < \cdots < g_s < N$ 
be integer parameters. 
A $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graph is a graph
that contains vertices of degrees $k_1,k_2,\ldots,k_t$ but no other 
degrees and cycles of lengths $g_1,g_2,\dots,g_s$ but no other cycles of 
length $< N$. 
For any given set of parameters satisfying the above conditions,
we present an explicit construction of $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graphs  
and extend the concept of a cage (a smallest graph of given degree and girth) 
to that of a generalized cage -- a smallest 
$(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graph. We introduce several infinite
families of generalized cages and study their basic properties
in the context of connected, bipartite, and vertex-transitive graphs, 
as well as combinatorial configurations (in the context of multilaterals). 

\phantom{push footnotes down}
\end{abstract}

\section{Introduction}

The main motivation for our paper comes from \cite{bobgru&pis} that 
addressed among other topics the question of the existence of trivalent
graphs with certain prescribed and prohibited cycle lengths. 
This called, for example, for the construction of a trivalent
graph of girth $6$ that contains an $8$-cycle, no $10$-cycle and a 
$12$-cycle, and all the possible combinations of prescribed or prohibited
$6$-, $8$-, and $10$-cycles. The authors have been able to construct a 
trivalent graph for any combination of these, and became interested
in characterizing all possible combinations of cycle lengths for
regular graphs. In the original version of this paper, we were able 
to show that essentially any sequence of cycle lengths can be the 
beginning of the cycle spectrum of a finite graph of degree $k$. 
Only after solving our original problem, we found out that 
a more general version of the above problem has been considered 
by Sachs in 1963 \cite{sachs}. He was able to prove the following:

\begin{theorem}[\cite{sachs}] \label{thmsachs}
Corresponding to any two integers $k \geq 3$ and $N \geq 4$ and any $N-2$
integers $\alpha_3,\ldots,\alpha_N$ it is possible to construct an unlimited
number of mutually non-isomorphic connected regular graphs of degree $k$
without bridges or cut-vertices, which contain exactly $\alpha_i$ cycles
of length $i$ for $ i = 3, \ldots, N $ and in which all the cycles of 
length $ \leq N $ are mutually disjoint.
\end{theorem}

In our approach, we think of the problem of finding finite graphs with
prescribed degrees and girths as a 
generalization of the well-known $(k,g)$-{\em Cage Problem} \cite{exojaj}:

\begin{problem}
Given integers $ k \geq 2 $ and $ g \geq 3 $, construct a $k$-regular
graph of girth $g$ of the smallest possible order.
\end{problem}

The smallest $k$-regular graphs of girth $g$ are called $(k,g)${\em -cages}.
The aim of our paper is to generalize the well-known problem of finding
$(k,g)$-cages to that of finding {\em generalized cages} -- smallest graphs for
which we prescribe and limit both the vertex degrees and cycle lengths. 
Special cases of generalized cages have already been considered under several 
different settings. One of these directions allowed for extending the degrees
considered and involved the study of graphs of prescribed bi-degree and girth 
\cite{par&al, fur&al} or prescribed set of degrees and girth \cite{chagou&kap,balmar}.
In another direction, Harary and Kov\' acs introduced the problem of the 
construction of regular graphs with prescribed even and odd girth 
\cite{har&kov1, har&kov2}, a topic of considerable interest 
\cite{cam, bal&al, par&al,jia,xuwan&wan}. Obviously, each change of the original
requirements required a separate proof of the existence of finite graphs
with the characteristics under consideration. From this point of view, the 
graphs constructed in our proofs of Corollary~\ref{disc} and 
Theorem~\ref{thm:connected} serve as 
universal examples for all of the above generalizations of (the original)
concept of cages.

The precise definition of generalized cages we use in this paper 
proceeds as follows.
A {\em $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots, g_s;N)$-graph},
$2 \leq k_1 < k_2 < \cdots < k_t $, $3 \leq g_1 < g_2 < \cdots < g_s < N$,
is a graph that contains vertices of degrees $k_1,k_2,\ldots,k_t$ but no 
other degrees and cycles of lengths $g_1,g_2,\dots,g_s$ but no other cycles of 
length $< N$.
A $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)${\em -cage} is defined
accordingly. We need to stress that even though we specify the
degrees required of our graphs, we do not specify how many of the 
vertices that have the required degrees (beyond the fact that we always need
at least one vertex of the particular order) must exist and
we only prescribe the beginning of the cycle spectrum for our graphs 
(hence, specifically, we do not specify whether a cycle of length $N$ must
or must not exist).
Occasionally, in the case 
when we only want to limit the girth of the graphs up to $g_s$, 
we will leave out the
upper bound $N$, and will talk about the 
$(k_1,\ldots,k_t;g_1,\ldots,g_s;)$-graphs that are simply graphs with 
the required degrees $k_1,\ldots,k_t$ (and no others) and cycles of the 
required lengths $g_1,\ldots,g_s$ (and no others of length $ \leq g_s $).
Similarly, the notation $(k_1,\ldots,k_t;;N)$ indicates graphs of girth at
least $N$.

The problem of finding $(k,g)$-cages has been quite popular during
the 1960's and 70's. After this initial period, the remaining problems were
deemed hard, and not much has been happening with regard to cages until
the introduction of algebraic and topological methods in the 1990's. 
These marked a revival of the topic with the focus on the construction of
infinite families of small graphs of given degree and girth (see, for example,
the survey paper \cite{exojaj}). 

Following this general trend, we focus specifically on topological constructions
and as a part of our treatise we investigate a 
construction that is a a generalization of the truncation construction 
particularly popular in topological graph theory. 
It is also a generalization of a method introduced
by Sachs in \cite{sachs} which helped him to prove Theorem~\ref{thmsachs}.
Using this construction in combination with the voltage graph construction, 
we prove a positive answer to the following question for all but the $1$-regular
graphs:

\begin{problem}\label{genprob}
Given integers $1 \leq k_1 < k_2 < \cdots < k_t $, 
$3 \leq g_1 < g_2 < \cdots < g_s < N$, does there exist 
a $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graph?
\end{problem}

Unlike the case of the original cages (which are all connected),
several generalized cages found in this paper turn out to be
disconnected (as seen, for example, in the first figure of our paper). 
In view of this, throughout the paper we 
are careful to stress the difference between the results 
concerning connected and disconnected graphs.
In the second half of our paper, in addition to proving the general existence of 
$(k_1,k_2,\ldots,k_t;g_1,g_2,\dots, g_s;N)$-graphs, 
we obtain bounds on the order of the 
$(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-cages, refine the problem
to the classes of connected, bipartite, and vertex-transitive graphs, 
and investigate the connection of such graphs to incidence structures.
%We also briefly address the question of characterizing the full
%cycle spectrum of graphs with prescribed degree set.

\section{The cases $k_1=1$ and $k_1=2$}

Before introducing our main construction,
note that graphs satisfying $k_1=1$ or $k_1=2$ 
(graphs possessing vertices of degree $1$ or $2$) are 
very easy to understand (see, for example, the next figure). 
Due to their simplicity, we deal with these cases first. 

\begin{figure}[ht] %\label{fig:case1} 
\centering
\begin{tikzpicture}
\draw (0,0)--(1,2);
\draw (1,2)--(2,0);
\draw (0,0)--(2,0);
\draw (0,3)--(2,3);
\fill [color=black] (0,0) circle (1.5pt);
\fill [color=black] (1,2) circle (1.5pt);
\fill [color=black] (0,3) circle (1.5pt);
\fill [color=black] (2,0) circle (1.5pt);
\fill [color=black] (2,3) circle (1.5pt);
%\draw (1,-0.8) node[below] {$(1,2;3;4)$-cage};
\end{tikzpicture} \hfil
\begin{tikzpicture}
\draw (0,0)--(1,2);
\draw (1,2)--(2,0);
\draw (0,0)--(2,0);
\draw (1,2)--(1,3);
\fill [color=black] (0,0) circle (1.5pt);
\fill [color=black] (1,2) circle (1.5pt);
\fill [color=black] (2,0) circle (1.5pt);
\fill [color=black] (1,3) circle (1.5pt);
%\draw (1.5,-0.8) node[below] {$(1,2,3;3;4)$-cage};
\end{tikzpicture} 
\caption{The unique $(1,2;3;4)$- and $(1,2,3;3;4)$-cages.} 
\label{fig:case1}
\end{figure}

\begin{theorem}\label{case1}

\begin{description}[topsep=0pt,partopsep=0pt,itemsep=2pt,parsep=2pt]
\item{(i)} There are no $(1;g_1,g_2,\dots,g_s;N)$-graphs.
\item{(ii)} A $(1,2;g_1,g_2,\ldots,g_s;N)$-graph exists for every set of parameters
$ 3 \leq g_1 < \cdots < g_s$, but there are no connected $(1,2;g_1,g_2,\ldots,g_s;
N)$-graphs.
\item{(iii)} If $k_1=1$ and $t>1$, a $(1,k_2,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$-graph 
exists if a $(k_2,\ldots,k_t;$ $g_1,g_2,\ldots,g_s;N)$-graph exists.
\item{(iv)} If $k_1=1$ and $t>1$, a connected 
$(k_1,k_2,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$-graph  
exists if there exists a connected 
$(k_2',\ldots,k_t';g_1,g_2,\ldots,g_s;N)$-graph satisfying the property 
$  k_i' \leq k_i $ for all $ 2 \leq i \leq t$ and $ k_i' < 
k_i $ for at least one $i$. 
\end{description}
\end{theorem}
\begin{proof}
There are no cycles in $1$-regular graphs and no graph containing 
cycles and only vertices of degrees $1$ and $2$ is connected. To complete
the proof of item $(ii)$, note that a disjoint union of $g_i$-cycles
${\cal C}_{g_i}$, $ 1 \leq i \leq s $, and a single edge is a disconnected
$(1,2;g_1,g_2,\ldots,g_s;N)$-graph.
Item $(iii)$ can be proved by adding two vertices joined by a single edge which 
makes a $(k_2,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$-graph into a disconnected 
%\newline
$(1,k_2,\ldots,k_t$; $g_1,g_2,\ldots,g_s;N)$-graph.
Similarly for $(iv)$, connecting extra edges
to vertices of degree $k_i' < k_i$ makes a connected
$(k_2',\ldots,k_t';g_1,g_2,\ldots,g_s;N)$-graph satisfying the property 
from the theorem into a connected 
%\newline
$(1,k_2,\ldots,k_t; g_1,g_2,\ldots,g_s;N)$-graph.
\end{proof}

While the order $n(1,k_2,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$ of the smallest
%\newline
$(1,k_2,\ldots,k_t; g_1,g_2,\ldots$, $g_s;N)$-graph can be deduced from the 
above constructions, it is ultimately not completely easy
to determine. For example, a straightforward analysis of all possible 
cases shows that the smallest $(1,2;3;4)$-graph is simply the
$3$-cycle united with a single disconnected edge, $n(1,2;3;4)=5$,
and the smallest $(1,2,3;3;4)$-graph is the $3$-cycle with a pendant edge
attached at one of the vertices, $n(1,2,3;3;4)=4$ (see figure above).
Somewhat surprisingly, the generalized cage with a larger set of degrees and the 
same set of required girths happens to be of a smaller order.

The case when we allow for degree $2$ is of a slightly different
nature. 

\begin{theorem} \label{case2}
\begin{description}[topsep=0pt,partopsep=0pt,itemsep=2pt,parsep=2pt]
\item{(i)} If $k_1=2$ and $t=1$,
a $(2;g_1,g_2,\ldots,g_s;N)$-graph exists for every set of parameters
$ 3 \leq g_1 < g_2 < \cdots <g_s$ and
every $(2;g_1,g_2,\ldots,g_s;N)$ graph is a
disjoint union of (at least one for each $g_i$) cycles of lengths 
$g_1,g_2, \ldots,g_s$, combined (possibly) with cycles of length $\geq N$.
\item{(ii)} There are no connected $(2;g_1,g_2,\ldots,g_s;N)$-graphs 
for $s$ bigger than $1$ and the $(2;g_1$, $g_2,\ldots,g_s;N)$-cages 
are of order $g_1+g_2+\cdots+g_s$, consist of disjoint unions of single 
copies of $g_i$-cycles, $ 1 \leq i \leq s $, and are the unique 
$(2;g_1,g_2,\ldots,g_s;N)$-graphs of that order.
\item{(iii)} If $k_1=2$ and $t>1$, 
there exist connected
$(2,k_2,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$-graphs
for any choice of the parameters $ 2 < k_2 < \cdots k_t $ and 
$3 \leq g_1 < g_2 < \cdots < g_s < N$. 
\end{description}
\end{theorem}
\begin{proof}
The case $t=1$ follows from the fact that all $2$-regular graphs 
consist of disjoint cycles.

If $k_i = 2m$ for $m>1$, joining $m$ cycles through a single vertex 
results in a vertex of degree $k_i$ and all other vertices of degree $2$.
If, on the other hand, $k_i=2m+1$, $m \geq 1$, joining two bouquets 
of $m$ cycles through a single edge results in two vertices of degree
$k_i$ and all other vertices of degree $2$. It is not hard to see that
further manipulation together with choosing the right cycle lengths can 
result in connected $(2,k_2,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$-graphs.
\end{proof}

Again, the order of a smallest 
$(2,k_2,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$-graph can be determined from
the above constructions but may be tricky to find. For example,
$n(2,3;3,5;6)=6$ as the $(2,3;3,5;6)$-cage is $3$-cycle sharing an edge
with a $5$-cycle, while $n(2,3;3,4;6)=4$ as the $(2,3;3,4;6)$-cage is the
$4$-cycle with a chord. 

\begin{figure}[ht] %\label{fig:case1b}
\centering
\begin{tikzpicture}
\draw (0,0)--(1,1);
\draw (0,0)--(1,-1);
\draw (1,1)--(1,-1);
\draw (1,-1)--(2,0);
\draw (1,1)--(2,0);
\fill [color=black] (0,0) circle (1.5pt);
\fill [color=black] (1,1) circle (1.5pt);
\fill [color=black] (1,-1) circle (1.5pt);
\fill [color=black] (2,0) circle (1.5pt);
%\draw (1.5,-1.2) node[below] {$(2,3;3,4;6)$-cage};
\end{tikzpicture} \hfil
\begin{tikzpicture}
\draw (0,0)--(1,1);
\draw (1,1)--(1,-1);
\draw (1,1)--(2,1);
\draw (0,0)--(1,-1);
\draw (1,-1)--(2,-1);
\draw (2,1)--(3,0);
\draw (2,-1)--(3,0);
\fill [color=black] (0,0) circle (1.5pt);
\fill [color=black] (1,1) circle (1.5pt);
\fill [color=black] (1,-1) circle (1.5pt);
\fill [color=black] (2,1) circle (1.5pt);
\fill [color=black] (2,-1) circle (1.5pt);
\fill [color=black] (3,0) circle (1.5pt);
%\draw (1.5,-1.2) node[below] {$(2,3;3,5;6)$-cage};
\end{tikzpicture} \hfil
\caption{The unique $(2,3;3,4;6)$- and $(2,3;3,5;6)$-cages.}
\label{fig:case1b}
\end{figure}


In view of these results, we shall assume from 
now on that $k_1 \geq 3$.

\section{Generalized truncation construction} \label{sec-gen-trun}

The truncation of a map is well-known construction from 
topological graph theory in which one saws off the vertices of a map
(an embedding of a graph into a surface) 
together with small immediate neighborhoods 
and then attaches cycles in their place \cite{grotuc}. 
Our main construction is a generalization of this construction.

Let $G$ be a finite graph with the {\em degree set} $\{ d_1,d_2,\ldots,d_t \}$ (i.e.,
the degree $d_v$ of each vertex $v \in V(G)$ is equal to exactly one of 
the $d_i$'s). Each edge of $G$ can be associated with two opposing
{\em directed edges}, each of which starts at other end-vertex of the edge. 
Let $D(G)$ denote the set of these oriented edges; note that $|D(G)|=2|E(G)|$.
While orientable topological maps naturally come with an inherent ordering of the
oriented edges emanating from a vertex, in the case of graphs, we are free to choose 
this ordering ourselves:
A {\em vertex-neighborhood labeling} of $G$ is a function $\rho$ from the 
set $D(G)$ into the set of positive integers that orders the oriented edges 
adjacent to the vertices of $G$, i.e., a function that maps the oriented edges 
starting from a vertex $v$ bijectively onto the set $ \{ 1, 2, \ldots, d_v \} $, for 
all $v \in V(G)$.

We note that every vertex-neighborhood labeling of a connected graph $G$ uniquely determines
an orientable embedding of $G$ \cite{grotuc}. In that sense, the truncation of a graph 
$G$ with a vertex neighborhood labeling $\rho$ is simply a truncation of a specific 
embedding of $G$.
The main difference between our truncation and the topological truncation, in which 
vertices are always replaced by cycles, lies in the fact that we truncate by all kinds of graphs:
Let $H_1,H_2, \ldots, H_t$ be a family of graphs 
of orders $d_1,d_2,\ldots,d_t$, respectively, 
with the vertices of the $H_i$'s labeled by the numbers 
$1,2,\ldots, |V(H_i)| = d_i$, for $1 \leq i \leq t$. 
%We say that the labeled 
%family $H_1,H_2, \ldots,
%H_t$ is a {\em truncation family} for the graph/vertex-neighborhood labeling pair $(G,\rho)$. 
The {\em generalized truncation of the graph} $G$ {\em with a vertex-neighborhood
labeling} $\rho$ {\em by the family} $H_1,H_2,\ldots,H_t$ is the graph 
$T(G,\rho; H_1,H_2,\ldots,H_t)$ obtained from $G$ by replacing {\em each} of the vertices
of $G$ by one the graphs $H_i$
according to the following rule: Let $v$ be a vertex
of $G$ of degree $d_i$, and let $e_i$, $ 1 \leq i \leq d_i$, be the oriented edges 
emanating from $v$ labeled according to the vertex-neighborhood labeling $\rho$, 
i.e., labeled so that $ \rho(e_i) = i $. Then, $v$ is replaced by the graph $H_i$ of order 
$d_i$ by first removing the vertex $v$ together with a part of each of the edges $e_i$,
$1 \leq i \leq d_i$, and then attaching $H_i$ to the oriented edges $e_i$ in such a way 
so that a vertex of $H$ labeled by $i$ is attached to the edge $e_i$. An example of one
such local truncation is included in Figure~\ref{fig:truncation} in which a vertex of degree
$4$ is replaced by a labeled $4$-cycle with a chord. 

\begin{figure} %\label{fig:truncation}
\centering
\begin{tikzpicture}
\draw (0,0)--(1,1);
\draw (0,0)--(1,-1);
\draw (0,0)--(-1,1);
\draw (0,0)--(-1,-1);
\fill [color=black] (0,0) circle (1.5pt);
\fill [color=black] (1,1) circle (1.5pt);
\fill [color=black] (1,-1) circle (1.5pt);
\fill [color=black] (-1,-1) circle (1.5pt);
\fill [color=black] (-1,1) circle (1.5pt);
%\draw (0,0) node[below] {$v$};
\draw (0.5,0.5) node[above] {$1$};
\draw (0.5,-0.5) node[below] {$2$};
\draw (-0.5,-0.5) node[below] {$3$};
\draw (-0.5,0.5) node[above] {$4$};
%\draw (1,1) node[below] {$v_1$};
%\draw (1,-1) node[below] {$v_2$};
%\draw (-1,-1) node[below] {$v_3$};
%\draw (-1,1) node[below] {$v_4$};
\end{tikzpicture} \hfil 
\begin{tikzpicture}
\draw (0,1) node[above] {$\Rightarrow$};
\end{tikzpicture} \hfil 
\begin{tikzpicture}
\draw (0.5,0.5)--(1,1);
\draw (0.5,-0.5)--(1,-1);
\draw (-0.5,0.5)--(-1,1);
\draw (-0.5,-0.5)--(-1,-1);
%\fill [color=black] (0,0) circle (1.5pt);
\fill [color=black] (1,1) circle (1.5pt);
\fill [color=black] (1,-1) circle (1.5pt);
\fill [color=black] (-1,-1) circle (1.5pt);
\fill [color=black] (-1,1) circle (1.5pt);
%\draw (0,0) node[below] {$v$};
%\draw (1,1) node[below] {$v_1$};
%\draw (1,-1) node[below] {$v_2$};
%\draw (-1,-1) node[below] {$v_3$};
%\draw (-1,1) node[below] {$v_4$};
\draw (0.5,0.5) node[above] {$1$};
\draw (0.5,-0.5) node[below] {$2$};
\draw (-0.5,-0.5) node[below] {$3$};
\draw (-0.5,0.5) node[above] {$4$};
\end{tikzpicture} \hfil
\begin{tikzpicture}
\draw (0,1) node[above] {$\Rightarrow$};
\end{tikzpicture} \hfil 
\begin{tikzpicture}
\draw (0.5,0.5)--(1,1);
\draw (0.5,-0.5)--(1,-1);
\draw (-0.5,0.5)--(-1,1);
\draw (-0.5,-0.5)--(-1,-1);
\draw (0.5,0.5)--(0.5,-0.5);
\draw (0.5,0.5)--(-0.5,0.5);
%\draw (0.5,0.5)--(-0.5,-0.5);
\draw (-0.5,-0.5)--(0.5,-0.5);
\draw (-0.5,0.5)--(0.5,-0.5);
\draw (-0.5,0.5)--(-0.5,-0.5);
%\fill [color=black] (0,0) circle (1.5pt);
\fill [color=black] (1,1) circle (1.5pt);
\fill [color=black] (1,-1) circle (1.5pt);
\fill [color=black] (-1,-1) circle (1.5pt);
\fill [color=black] (-1,1) circle (1.5pt);
\fill [color=black] (0.5,0.5) circle (1.5pt);
\fill [color=black] (0.5,-0.5) circle (1.5pt);
\fill [color=black] (-0.5,-0.5) circle (1.5pt);
\fill [color=black] (-0.5,0.5) circle (1.5pt);
%\draw (0,0) node[below] {$v$};
%\draw (1,1) node[below] {$v_1$};
%\draw (1,-1) node[below] {$v_2$};
%\draw (-1,-1) node[below] {$v_3$};
%\draw (-1,1) node[below] {$v_4$};
\draw (0.5,0.5) node[above] {$1$};
\draw (0.5,-0.5) node[below] {$2$};
\draw (-0.5,-0.5) node[below] {$3$};
\draw (-0.5,0.5) node[above] {$4$};
\end{tikzpicture}
\caption{Truncation of a vertex of degree $4$ by a $4$-cycle with a chord} 
\label{fig:truncation}
\end{figure}
%\vskip 5mm

The significance of the generalized truncation construction in constructing 
graphs with prescribed and prohibited degrees and cycles is summarized 
in the following theorem.

\begin{theorem} \label{trunc}
Let $G$ be a finite $(d_1,d_2,\ldots,d_t;g)$-graph with vertex-neighborhood 
labeling $\rho$. Let $H_1,H_2,\ldots,H_t$ be a truncation family for $(G,\rho)$
of labeled 
%\newline 
$(k_1^i,\ldots,k_{t_i}^i; g_i) $-graphs, $1 \leq i \leq t $.

The generalized truncation graph $\tilde{G} = T(G,\rho; H_1,H_2,\ldots,H_t)$ 
is a $(K;g)$ graph of girth not smaller than 
$ g_{min} = \min \{ 2g,g_1,g_2,\ldots,g_t \} $, and degree set 
$K = \{ k_i^j + 1 \; | \; 1 \leq i \leq t_j, 1 \leq j \leq t \} $.

Moreover, if both $G$ and the $H_i$'s are connected, so is $\tilde{G}$, 
and if $g_{min} < 2g $, then $g_{min}$ is the exact girth of 
$\tilde{G}$.
\end{theorem}
\begin{proof} 
In $\tilde{G}$, color the new edges (the edges of the graphs $H_i$)
red, and the old edges (the original edges of $G$) blue. The blue edges
form a $1$-factor of $\tilde{G}$, and  each vertex $v$ of $\tilde{G}$
is incident with one blue edge and $k_i^j$ red edges of $\tilde{G}$
(for some $ 1 \leq i \leq t_j, 1 \leq j \leq t $). Thus, the degree set of
$\tilde{G}$ equals 
$K = \{ k_i^j + 1 \; | \; 1 \leq i \leq t_j, 1 \leq j \leq t \} $, as claimed.
Furthermore, no cycle ${\cal C}$ of $\tilde{G}$ has two consecutive blue edges, 
and we have two possibilities to consider. If ${\cal C} $ contains no blue 
edges at all, it is completely red, and its vertex set must be a subset of
a copy of $H_i$ for some $1 \leq i \leq t$. Thus, in this case, ${\cal C}$
is a cycle of $H_i$ and its length must be $ \geq g_i$.
The other possibility is that ${\cal C}$ contains both red and blue edges.
For any $2$-colored cycle, if we remove the red edges, the sequence of blue
edges is non-repeating and any two adjacent blue edges (with a red path
between them) must have been adjacent in $G$. Thus, the blue edges constitute
a walk in the original graph $G$ that contains at least one cycle of $G$, and
the red/blue cycle is of length at least $2g$. The last statement
of our theorem follows from the fact that $\tilde{G}$ contains a red cycle 
of length $g_i$ for each $ 1 \leq i \leq s $. The connectivity of $\tilde{G}$
in the case when both $G$ and the $H_i$'s are connected is easy to see.
\end{proof}

Note that the above proof shows an even stronger result. Namely, in the 
case when all the graphs $H_i$ are connected, each cycle 
${\cal C}$ of the graph $G$ is `lifted' into a cycle of the graph 
$\tilde{G}$ with the length of the lifted cycle being {\em at least} twice 
the length of ${\cal C}$.

\section{Disconnected $(k_1,\ldots,k_t;g_1,\ldots,g_s;N)$-graphs}

In this section, we solve the general question
of the existence of $(k_1,\ldots,k_t;g_1,\ldots,g_s;N)$-graphs. 
As stated in the introduction, we will construct such graph for every set 
of parameters $2 \leq k_1 < k_2 < \cdots < k_t $ and
$3 \leq g_1 < g_2 < \cdots < g_s < N$. It is important to note that if we
do not require the graph to be connected, the problem is quite a bit easier 
to handle. As in the case of the $2$-regular graphs covered in 
Theorem~\ref{case2}, we can compose the 
$(k_1,\ldots,k_t;g_1,\ldots,g_s;N)$-graph
of disconnected components, each of them being a $(k;g;N)$-graph,
$k \in \{ k_1,\ldots,k_t \}$, $g \in \{ g_1, \ldots, g_s \} $.
Our main claim thus follows from the following theorem that is a 
special case of the more general Theorem~\ref{thmsachs} of Sachs.
Its proof provides us with a nice example of the use
of the generalized truncation.

\begin{theorem}
Let $k \geq 2$ and $3 \leq g < N$. Then there exists a $(k;g;N)$-graph.
\end{theorem}
\begin{proof}
We proceed by induction on $k$. 
The case of $k=2$ has been settled in Theorem~\ref{case2}. The graph can be
taken to be a single $g$-cycle.

For $k=3$, let $G$ be any $(g,\lceil \frac{N}{2} \rceil)$-graph (the 
existence of which is guaranteed for example by the result of \cite{sachs}).
Note that $g$ is the degree of the graph while $\lceil \frac{N}{2} \rceil$
is its girth. Let $H$ be the $g$-cycle, and $\rho$ be any vertex-neighborhood
labeling of $G$. It follows from Theorem~\ref{trunc} that the generalized 
truncation graph $T(G,\rho;H)$ is a $(3;g;N)$-graph.

For the induction step, assume the existence of a $(k;g;N)$-graph $H$ for some
$ k \geq 2 $ and $3 \leq g \leq N$ of order $n$. 
Let $G$ be any $n$-regular graph of girth at least $\lceil \frac{N}{2} \rceil$ 
(guaranteed again by \cite{sachs}), and let 
$\rho$ be any vertex-neighborhood labeling of $G$. 
Theorem~\ref{trunc} asserts that the truncated graph 
$T(G,\rho;H)$ is a $(k+1;g;N)$-graph.
\end{proof}

\begin{corollary} \label{disc}
Let $ 1 \leq k_1 < k_2 < \cdots < k_t $ and 
$3 \leq g_1 < g_2 < \cdots < g_s < N$. If $k_1 \geq 2$ or
$t>1$, then there
exists a $(k_1,\ldots,k_t;g_1,\ldots,g_s;N)$-graph.
\end{corollary}
\begin{proof}
If $k_1 \geq 2$, the graph can be taken to be the disjoint union of graphs $G_{i,j}$,
where $G_{i,j}$ is a $(k_i;g_j;N)$-graph whose existence is guaranteed by  
Theorem~\ref{trunc}, $1 \leq i \leq t, 1 \leq j \leq s$. If $t>1$, the result follows from
Theorem~\ref{case1} $(iii)$.
\end{proof}

The reader may find it a bit disappointing that we broke the intriguing 
problem of mutually coexisting cycles into separate problems by constructing
a disconnected graph. As seen in Theorem~\ref{case2}, the disconnectedness
of our solution may appear inherent to the problem. This is however not the
case, and the only sets of parameters that do not allow for connected graphs
are those from Theorems \ref{case1} and \ref{case2}.
In the next two sections we will construct 
{\em connected} $(k_1,\ldots,k_t;g_1,\ldots,g_s;N)$-graphs for all other
parameter sets.

\section{Voltage graph lifts}

Our construction of {\em connected} $(k;g_1,g_2,\ldots,g_s;N)$-graphs
includes the use of a lift of a graph with a voltage assignment (see, e.g.,
\cite{grotuc}). 
We briefly describe this method and prove the existence of a 
connected graph with properties needed for our main construction.

The {\em base graph} $B$ is allowed to have multiple edges 
and multiple loops and we replace each edge and loop of $B$ by a pair 
of opposing (oriented) {\em darts} (with $D(B)$ denoting the set of darts 
of $B$).
A {\em voltage assignment} on $B$ is any mapping $\alpha$
from $D(B)$ into a group $\Gamma$ that satisfies the condition 
$ \alpha(e^{-1}) = (\alpha(e))^{-1} $ for all $ e \in D(B)$.

The {\em derived regular cover (lift)} of $B$ with respect 
to the voltage assignment $\alpha$ is denoted by $B^{\alpha}$, and
has the vertex set $ V(B) \times \Gamma$ (written in the form $u_g$,
$ u \in V(B), g \in \Gamma $). Two vertices $ u_g $ and $ v_f $ are 
adjacent in $B^{\alpha}$ if $ e=(u,v) \in D(B) $ and $ f = g \cdot \alpha(e) $.
The set of vertices $\{ u_g \; | \; g \in \Gamma  \} $ is called the {\em
fiber} of $u$. If ${\cal C} = e_1,e_2,\ldots,e_{\ell} $ is an oriented
cycle of $B$, the product $f=\alpha(e_1) \cdot \alpha(e_2) \cdot \cdots \cdot 
\alpha(e_{\ell})$ (in $\Gamma$) is called the {\em net voltage} of ${\cal C}$,
and a lift of ${\cal C}$ is a cycle of length equal to the $lcm(\ell,|f|)$,
where $|f|$ denotes the order of $f$ in $\Gamma$.

A lift of $B$ is said to be {\em cyclic} if the voltage group 
used is a cyclic group $\ZZ_n$ of order $n$ (which we will write in the 
additive notation).

We are ready to prove the main theorem of our section. 

\begin{lemma} \label{lift}
Let $k \geq 2$, $ g \geq 3$, and $B$ be a $(k,g)$-graph. Let $z \geq 1$.
Then there exists a cyclic lift $B^{\alpha}$ that contains a 
connected component $G$ such that 
\begin{description}[topsep=0pt,partopsep=0pt,itemsep=2pt,parsep=2pt]
\item{(i)} $G$ is $k$-regular,
\item{(ii)} the girth of $G$ is at least $g$, 
\item{(iii)} no $2$ vertices of $G$ that belong to the same fiber share mutual 
neighbors, and 
\item{(iv)} at least one fiber of $G$ contains at least $z$ vertices.
\end{description}
\end{lemma}
\begin{proof} Let $B$ be a $k$-regular graph of girth $g$ and order $n$. 
Take $m > z \cdot n$ and relatively prime to $g$ and let $u$ be a vertex of $B$ that lies on
a $g$-cycle of $B$. Choose a direction for the $g$-cycle containing $u$ and
define a voltage assignment $\alpha$ from $D(B)$ into $\ZZ_m$ by 
assigning $1$ to one of each pair of opposing darts of $B$
and $-1$ to the opposite dart in such a way that the darts of the $g$-cycle
containing $u$ oriented along the direction chosen for this cycle all receive the
voltage $1$. Let $(u,g)$ be any lift of $u$ in $B^{\alpha}$, and let 
$G$ be the connected component of $(u,g)$.
Then $G$ satisfies the conditions of our lemma. 

First, each vertex
of $B^{\alpha}$ is of degree $k$, and so must be the degree of each vertex
of $G$.

Consider a cycle ${\cal C}$ of $B^{\alpha}$ of length $\ell$. 
If ${\cal C}$ contains no two vertices from the same fiber of $B^{\alpha}$
(other than the beginning and end vertex), 
the projection of ${\cal C}$ into $B$ must be a cycle of $B$ of length $\ell$
as well, and hence $\ell \geq g $. If ${\cal C}$ does contain at least two
vertices of the same fiber, it contains a sub-path ${\cal P}$ whose 
end-points belong to the same fiber, but no other two vertices do. The
projection of ${\cal P}$ into $B$ cannot be a self-reversing path as the base
graph $B$ has no loops and no multiple edges and thus the projection 
is a cycle of $B$, and hence $\ell \geq g$
again. It follows that the girth of $G$ is at least $g$.

Let $v_f,v_h \in V(G)$, and suppose that there exists a vertex $w_r$ that
is a mutual neighbor of $v_f$ and $v_h$. Then there must exist an edge $e$
of $B$ that connects $v$ and $w$. Suppose that the voltage of the dart from
$v$ to $w$ is $a$ (where $a$ is either $1$ or $-1$). 
Since $w_r$ is a neighbor of $v_f$, $r=f+a$. Similarly,
since $w_r$ is a neighbor of $v_h$, $r=h+a$. But $f$ and $h$ were assumed 
different, and we obtain a contradiction.

Finally, it is not hard to see that the order of $G$ is at least $m$ (the
order of the voltage group). The argument is quite simple. Let ${\cal C}$
be the $g$-cycle through $u$ whose edges have been assigned $1$'s in 
accordance with its direction. Then the net voltage of ${\cal C}$ is 
equal to $g$, and the length of each lift of ${\cal C}$ in $B^{\alpha}$ is equal to 
$g \cdot |g|$ where $|g|$ denotes the order of $g$ in $\ZZ_m$. 
Since $m$ is assumed to be relatively prime to $g$, the order of $g$ in $\ZZ_m$ 
is $m$ and hence the lift of ${\cal C}$ passing through
$u_g$ is a cycle of length $gm$. As all the vertices of ${\cal C}$ belong
to $G$, the order of $G$ is greater than $m > z \cdot n$, where $n$ is the number of 
fibers. By the Pigeonhole Principle, $G$ contains at least $z$ vertices 
of at least one fiber of $B^{\alpha}$. 
\end{proof}

\section{Connected $(k_1,\ldots,k_t;g_1,\ldots,g_s;N)$-graphs}

We prove the existence of a connected 
$(k_1,\ldots,k_t;g_1,\ldots,g_s;N)$-graph 
for each set of parameters satisfying the condition $k_1 \geq 3$.
It is once again the 
case that the first part of our proof, namely the part where we prove the existence
of the $(k_1;g_1,g_2,\dots,g_s;N)$-graphs, can already be deduced from Theorem~\ref{thmsachs} (but we prove it differently). Graphs with varied degrees are then obtained
by extending the initial $(k_1;g_1,g_2,\dots,g_s;N)$-graphs.

% $G$ be a graph and $S \subseteq V(G)$. Let $ \{ d_1,d_2,\ldots,d_t \} $ be the degree set 
%for the vertices in $S$ and $\rho$ be a vertex-neighborhood labeling for the directed edges 
%emanating from the vertices in $S$.
%Let $H_1,H_2, \ldots, H_t$ be a family of graphs 
%of orders $d'_1,d'_2,\ldots,d'_t$ satisfying the inequalities $d'_i \geq d_i$, and let $S_i 
%\subseteq V(H_i)$, $|S_i|=d_i$, be subsets labeled bijectively by the numbers 
%$ \{ 1,2,\ldots,d_i \}$, for each $ 1 \leq i \leq t $.
%The {\em relaxed generalized truncation of the graph} $G$ with $S \subseteq V(G)$ and 
%vertex-neighborhood labeling $\rho$ by the family $H_1,H_2,\ldots,H_t$ is the graph 
%$RT(G,S,\rho; H_1,H_2,\ldots,H_t)$ obtained from $G$ by replacing 
%the vertices in $S$ by the graphs $H_i$
%according to the following rule: Let $v$ be a vertex
%in $S$ of degree $d_i$, and let $e_j $, $ 1 \leq j \leq d_i$, be the oriented edges 
%emanating from $v$ labeled according to the vertex-neighborhood labeling $\rho$, 
%i.e., labeled so that $ \rho(e_j) = j $. Then, $v$ is replaced by the graph $H_i$ by first %removing the vertex $v$ together with a part of each of the edges $e_j$,
%$1 \leq j \leq d_i$, and then attaching the vertices in $S_i$ to the oriented edges $e_j$ in %such a way 
%so that a vertex labeled by $j$ is attached to the edge $e_j$. 

%Even though this latest definition sounds somewhat like the definition of the 
%original truncation in Section~\ref{sec-gen-trun}, the main differences between
%the two constructions lie in the facts that not all the vertices of $G$ are being truncated and
%not all the vertices of the graphs $H_i$
%are being attached to the edges originally attached to the vertex that is
%being removed (only the $d_i$ selected vertices of $H_i$ are being attached).
%This means, in particular, that the degrees of the vertices in $V(G)$ which do not belong to %the set
%$S$ and the vertices in $V(H_i)$ which do not belong to the sets $S_i$, $ 1 \leq i \leq t$,  %remain unchanged after the truncation.

%An example of the relaxed local truncation of a single vertex is included in 
%Figure~\ref{fig:rtruncation} in which a vertex of degree
%$4$ is replaced by a $6$-cycle with a chord in which four of the vertices are selected and %labeled by the 
%numbers $1,2,3,$ and $4$, and two of the vertices are not selected and labeled and whose %degrees remain unchanged.

%The proof of the following lemma follows along the same lines as the proof 
%of Theorem~\ref{trunc}; it is left to the reader.

%\begin{lemma} \label{gen-trunc}
%Let $G$, $\rho$, and $H_1,H_2,\ldots,H_t$ be as described above, let $g$ be the girth of %%$G$, and
%let $g_i$, $ 1 \leq i \leq t $, denote the girths of the $H_i$'s. 
%Then, the relaxed generalized truncation $\tilde{G} = RT(G,S,\rho; H_1,H_2,\ldots,H_t)$ 
%is a graph of girth not smaller than 
%$ g_{min} = \min \{ g,g_1,g_2,\ldots,g_t \} $, and if $G$ and the $H_i$'s, $ 1 \leq i \leq t $,
%are connected, so is $\tilde{G}$. 
%\end{lemma}


%\begin{figure} \label{fig:rtruncation}
%\centering
%\begin{tikzpicture}
%\draw (0,0)--(1,1);
%\draw (0,0)--(1,-1);
%\draw (0,0)--(-1,1);
%\draw (0,0)--(-1,-1);
%\fill [color=black] (0,0) circle (1.5pt);
%\fill [color=black] (1,1) circle (1.5pt);
%\fill [color=black] (1,-1) circle (1.5pt);
%\fill [color=black] (-1,-1) circle (1.5pt);
%\fill [color=black] (-1,1) circle (1.5pt);
%\draw (0,0) node[below] {$v$};
%\draw (1,1) node[below] {$v_1$};
%\draw (1,-1) node[below] {$v_2$};
%\draw (-1,-1) node[below] {$v_3$};
%\draw (-1,1) node[below] {$v_4$};
%\end{tikzpicture} \hfil 
%\begin{tikzpicture}
%\draw (0,1) node[above] {$\Rightarrow$};
%\end{tikzpicture} \hfil 
%\begin{tikzpicture}
%\draw (0.5,0.5)--(1,1);
%\draw (0.5,-0.5)--(1,-1);
%\draw (-0.5,0.5)--(-1,1);
%\draw (-0.5,-0.5)--(-1,-1);
%\fill [color=black] (0,0) circle (1.5pt);
%\fill [color=black] (1,1) circle (1.5pt);
%\fill [color=black] (1,-1) circle (1.5pt);
%\fill [color=black] (-1,-1) circle (1.5pt);
%\fill [color=black] (-1,1) circle (1.5pt);
%\draw (0,0) node[below] {$v$};
%\draw (1,1) node[below] {$v_1$};
%\draw (1,-1) node[below] {$v_2$};
%\draw (-1,-1) node[below] {$v_3$};
%\draw (-1,1) node[below] {$v_4$};
%\end{tikzpicture} \hfil
%\begin{tikzpicture}
%\draw (0,1) node[above] {$\Rightarrow$};
%\end{tikzpicture} \hfil 
%\begin{tikzpicture}
%\draw (0.5,0.5)--(1,1);
%\draw (0.5,-0.5)--(1,-1);
%\draw (-0.5,0.5)--(-1,1);
%\draw (-0.5,-0.5)--(-1,-1);
%\draw (0.5,0.5)--(0.5,-0.5);
%\draw (0.5,0.5)--(-0.5,0.5);
%\draw (0.5,0.5)--(-0.5,-0.5);
%\draw (-0.5,-0.5)--(0.5,-0.5);
%\draw (-0.5,0.5)--(0.5,-0.5);
%\draw (-0.5,0.5)--(-0.5,-0.5);
%\draw (-0.5,0.5)--(-0.8,0);
%\draw (-0.5,-0.5)--(-0.8,0);
%\draw (0.5,0.5)--(0.8,0);
%\draw (0.5,-0.5)--(0.8,0);
%\fill [color=black] (0,0) circle (1.5pt);
%\fill [color=black] (1,1) circle (1.5pt);
%\fill [color=black] (1,-1) circle (1.5pt);
%\fill [color=black] (-1,-1) circle (1.5pt);
%\fill [color=black] (-1,1) circle (1.5pt);
%\fill [color=black] (0.5,0.5) circle (1.5pt);
%\fill [color=black] (0.5,-0.5) circle (1.5pt);
%\fill [color=black] (-0.5,-0.5) circle (1.5pt);
%\fill [color=black] (-0.5,0.5) circle (1.5pt);
%\fill [color=black] (-0.8,0) circle (1.5pt);
%\fill [color=black] (0.8,0) circle (1.5pt);
%\draw (0,0) node[below] {$v$};
%\draw (1,1) node[below] {$v_1$};
%\draw (1,-1) node[below] {$v_2$};
%\draw (-1,-1) node[below] {$v_3$};
%\draw (-1,1) node[below] {$v_4$};
%\draw (0.5,0.5) node[above] {$1$};
%\draw (0.5,-0.5) node[below] {$2$};
%\draw (-0.5,-0.5) node[below] {$3$};
%\draw (-0.5,0.5) node[above] {$4$};
%\end{tikzpicture}
%\caption{Truncation of a vertex of degree $4$ by a $6$-cycle with a chord and
%four labeled vertices} 
%\label{fig:rtruncation}
%\end{figure}
%\vskip 5mm

\begin{theorem} \label{thm:connected}
Let $ 2 < k_1 < \cdots < k_t $ and $3 \leq g_1 < \cdots < g_s < N$, and 
suppose that $ t>1 $ or $k_1 \geq 3$.
Then there exists a connected $(k_1,\ldots,k_t;g_1,\ldots,g_s;N)$-graph.
\end{theorem} 
\begin{proof}
For $t=1$ and $k_1=3$, let $B$ be any connected $(k',g')$-graph with $k',g' > max \{ N, 3 \} $, 
and let $G$ be the connected component of a lift of $B$ that we constructed in
Lemma~\ref{lift} with $ z = s $.
Then $G$ is of degree $k' > 3 $ and girth at least $g' > N$. 
Let $v_1,v_2,\ldots,v_s$ be the $s$ vertices that belong to the same
fiber of $B$ whose existence is guaranteed by Lemma~\ref{lift} (iv).
Then all their neighborhoods are mutually disjoint and each of the 
neighborhoods is of size $k'$. 
%For each of the numbers $k_i$, $1 \leq i \leq s$,
%decrease the degree of the vertex $v_i$ to $k_i$,
For each of the numbers $g_j$, $1 \leq j \leq t$, decrease the degree 
of the vertex $v_{j}$ to $g_j$ (by removing the appropriate number of adjacent edges).
The removal of these edges will result in a
graph $H$ with 
one vertex of degree $g_j$ for each $ 1 \leq j \leq s$, 
and the rest of the vertices of degrees $k'-1$ or $k'$ (depending on whether they had been a 
neighbor of a vertex whose degree has been decreased and the connecting edge has been 
removed or not). 
If $\rho$ is any vertex-neighborhood labeling of $H$, for each $ 1 \leq i \leq s$,
${\cal C}_{g_i}$ is a $g_i$-cycle labeled at random from $ \{ 1, \ldots, g_i \} $, 
and ${\cal C}_{k'-1}, {\cal C}_{k'} $ are randomly labeled $k'-1$ and $k'$-cycles, 
then the generalized truncated 
graph $T(H,\rho;{\cal C}_{g_1},{\cal C}_{g_2}, \ldots, {\cal C}_{g_s},{\cal C}_{k'-1},
{\cal C}_{k'})$ can be easily seen to be a $(3;g_1,g_2,\ldots,g_s;N)$-graph.
(Since $k'$ is taken to be greater than $N$, the cycles ${\cal C}_{k'-1}$ and ${\cal C}_{k'} $
do not have to be listed among the cycles shorter than $N$.)

The proof for the cases $t=1$ and $k_1>3$ can now be completed using the `usual' recursion 
via inserting a $(k-1;g_1,g_2,\ldots,g_s;N)$-graph of order $n$ into any $(n,g)$-graph
with $g > N$ to obtain a $(k;g_1,g_2,\ldots,g_s;N)$-graph.

Consider finally the case $t>1$ and $k_1 \geq 3 $. In this case, we construct the 
$(k_1,\ldots,k_t;$ $g_1,\ldots,g_s;N)$-graphs from the above $(k_1;g_1,g_2,\ldots,g_s;N)$-graph
$G$ by increasing the degrees of some of the vertices of the graph $G$ to the desired values 
$k_2, k_3, \ldots, k_t$. Let us assume without loss of generality that $G$ contains at least 
$t-1$
non-incident edges $e_2,\ldots,e_t$ with end-points $x_i,y_i$, $ 2 \leq i \leq t $,
respectively. Let $H$
be any connected $k_1$-regular graph of girth $ g > N+1$, let $e$ be an edge of $H$ with end-points
$x$ and $y$, and let $H'$ be the graph $H$ with the edge $e$ (but not the vertices $x,y$) removed.
For every $i$, $ 2 \leq i \leq t $, attach $ k_i - k_1 $ disjoint copies of $H'$ to the vertices $x_i,y_i$ with
each of the copies attached via a pair of edges connecting $x$ to $x_i$ and $y$ to $y_i$.
We claim that the resulting graph is our desired $(k_1,\ldots,k_t;g_1,\ldots,g_s;N)$-graph: 
The degrees of all but the vertices $x,y,x_i,y_i$, $ 2 \leq i \leq t $, remain unchanged (equal to $k_1$), 
the degrees the vertices of $x,y$ in each copy of $H'$ equal $k_1-1+1=k_1$, and the degrees of
the vertices $x_i,y_i$ clearly equal $k_i$, for all $ 2 \leq i \leq t $. Thus, the resulting graph has the 
correct degree sequence. As $G$ already contains cycles of all of the lengths $g_i$, $ 1 \leq i \leq s $,
and no edges have been removed from $G$, the resulting graph contains all the required cycles. 
It remains to show that the resulting graph does not
contain cycles of length smaller than $N$ that are not among the required ones. As no edges have been 
added between any two vertices of $G$, and no edges have been added between any two vertices of $H'$,
if such a cycle existed, it would have to contain edges from both $G$ and some copy of $H'$, and thus would
have to contain both vertices $x$ and $y$ of some copy of $H'$. However,
since the girth of $H$ was taken to be greater than $N+1$, any path between $x$ and $y$
that consists entirely of edges in $H'$ must be of length at least $N$ as otherwise this path together with the (removed) edge between 
$x$ and $y$ would have given rise to a cycle of length smaller than $N+1$.
Thus, any cycle of the resulting graph that contains both $x$ and $y$ must be longer 
than $N$, and therefore the resulting graph does not contain cycles that contain edges
from $G$ and some copy of $H'$ and are shorter than $N$.
This completes the proof of the theorem for this last case.
\end{proof}

We feel obliged to note that the above proof is a simplification of
our original proof.  This has been achieved using ideas submitted by
one of our referees.

\section{Bipartite $(k_1,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$-graphs and\\ 
configurations}

As mentioned in the introduction,
the motivation for considering bipartite graphs with these properties
comes from the study of combinatorial configurations \cite{bobgru&pis}.

A {\em $(v_k)$ configuration} is an incidence structure of $v$ points and $v$ lines
satisfying the properties 
that each line is incident with $k$ points, each point is incident with $k$ lines,
and any two distinct points are incident with at most one common line.
The {\em incidence graph} (also called a {\em Levi graph}) of a $(v_k)$ configuration
is a bipartite graph with the vertices in one bipartition set representing the points,
the vertices in the other bipartition set representing the lines, and the adjacency 
relation defined by the incidence relation in the configuration. 
From the definition
it immediately follows that a Levi graph of a $(v_k)$ configuration is a $k$-regular
graph of girth at least $6$. Conversely, each bipartite $k$-regular graph 
with girth at least $6$ determines a pair of mutually dual $(v_k)$ configurations.

A cycle of length $g$ (which is an even number) in the Levi graph of a 
configuration ${\cal C}$ corresponds to a $\frac{g}{2}$-lateral (or a $\frac{g}{2}$-gon)
in ${\cal C}$. Formally, an {\em $n$-lateral} (or an {\em $n$-gon}) in a configuration
is a cyclically ordered set 
$\{p_0, \ell_0, p_1, \ell_1, \ldots, p_{n-2}, \ell_{n-2},  p_{n-1}, \ell_{n-1}\}$
of pairwise distinct points $p_i$ and pairwise distinct lines $\ell_i$
such that $p_i$ is incident to $\ell_{i-1}$ and $\ell_i$.

The question posed in~\cite{grunbaum} (though in the context of geometric configurations)
and partially answered in~\cite{bobgru&pis} asks about all possible combinations 
of existence and non-existence of $n$-laterals in configurations. 
The same question (via Levi graphs) can be expressed as a problem
of existence of \emph{bipartite} $(k;g_1,g_2,\ldots,g_s;N)$-graphs, 
$6 \leq g_1 < g_2 < \cdots < g_s < N$, for each set of parameters with all
the $g_i$'s even.

%Note that all graphs constructed in \cite{bobgru&pis} came out bipartite.
%Also, all the known $(k,g)$-cages, $g$ even, are bipartite, and it has, 
%in fact, been conjectured that all even girth cages are bipartite. 
%(A $(k,g)$-cage is a $(k,g)$-graph of the smallest possible order.)

\begin{theorem} \label{thm:bipartite}
Let $3 \leq k_1 < \ldots < k_s$ and $4 \leq g_1 < g_2 < \ldots < g_s < N$, each $g_i$ even. 
Then there exists a (connected) bipartite $(k_1,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$-graph.
\end{theorem}
\begin{proof}
%Bipartite $(k;g_1,g_2,\ldots,g_s;N)$-graphs are very easy to construct.
%Assuming the obvious necessary condition that each of the $g_i$'s is even, 
If the $(k_1,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$-graph constructed in the proof of
Theorem~\ref{thm:connected},
is already bipartite, then we are done. Otherwise we construct its double 
cover -- a $\ZZ_2$ lift with each dart receiving the 
voltage $1$. The lifted graph is twice the size of the original, has only cycles
of even length, and most importantly, lifts even length cycles of the original
graph into cycles of the same length, and lifts odd cycles to cycles of doubled
size. Since all the edges of the lift go between the two copies of the original graph, 
the double cover of a $(k_1,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$-graph with all
$g_i$'s even is a bipartite graph that contains cycles of length $g_i$ for each 
$ 1 \leq i \leq s $. It remains to show that the lift does not contain cycles of `wrong' 
length.
Let ${\cal C}$ be any cycle of the lifted graph. If ${\cal C}$ contains no two
distinct vertices from the same fiber, ${\cal C}$ projects onto a base graph cycle, and
hence is of good length, as the base graph contains only cycles of good length.
If ${\cal C}$ contains two distinct vertices $u,v$ from the same fiber, since we have no
vertical edges within fibers, ${\cal C}$ contains a non-trivial path connecting
$u$ and $v$. Let ${\cal P}$ be a shortest sub-path of ${\cal C}$ that connects
two vertices from the same fiber. Then ${\cal P}$ projects onto a cycle of the 
base graph. As the end-points of the lift of this cycle are not the same vertex,
this cycle must be of odd length and hence of length at least $N$. It follows
that ${\cal C}$ is also of length at least $N$. Thus, the lifted graph is a
$(k_1,\ldots,k_t;g_1,g_2,\ldots,g_s;N)$-graph.
\end{proof}

The following corollary of the above theorem answers the related question
concerning configurations.
\begin{corollary}
Let $k \geq 3$ and $3 \leq n_1 < n_2 < \cdots < n_s < N$. Then there
exists a $(v_k)$ configuration that contains laterals of lengths 
$n_1, n_2, \ldots, n_s$ but no other laterals of length $ < N$. 
\end{corollary}
\begin{proof}
Using Theorem~\ref{thm:bipartite} construct a bipartite 
$(k;2n_1,2n_2,\dots,2n_s;2N)$-graph which is a Levi graph of the desired 
configuration.
\end{proof}

Combining the ideas from Section 5 with this Section we notice that if we want to extend the generalized girth problem to incidence graphs of non-balanced configurations, i.e. configurations with semi-regular bipartite Levi graphs, a special notation is needed.
In \cite{grunbaum}, there are several examples involving configurations with the symbol 
$(v_r,b_k)$, where
$v r = b k$ and the corresponding Levi graph has girth at least $6$, has  $v$ black vertices and $b$ white vertices, the black vertices have degree  $r$ and the white vertices have degree $k$. In our notation it is a 
bipartite $(r,k;;6)$ graph. In order to have more precise information, we have to amend the notation. Let 
$[k_1,k_2,\dots,k_t;g_1,g_2,\dots,g_s;N]$ denote a $(k_1,k_2,\dots,k_t;g_1,g_2,\dots,g_s;N)$ graph with a $t$-vertex coloring
and the property that each vertex of color $i$ has degree $k_i$. Using this notation we no longer require that the 
$k_i$ be distinct (and ordered). The generalized girth problem has now a special subproblem for  
$[k_1,k_2,\dots,k_t;g_1,g_2,\dots,g_s;N]$-graphs.

%(Marko should be able to find examples where the two problems have different solutions!!!)
 

\section{Vertex-transitive $(k;g_1,g_2,\ldots,g_s;N)$-graphs}

A graph $G$ is called {\em vertex-transitive\/} if for any ordered 
pair $(u,v)$ of vertices of $G$ there exists an automorphism 
$ \phi $ of $G$ such that $ \phi(u)=v $. As every vertex-transitive graph
must be $k$-regular for some $k$, 
none of the non-regular graphs constructed so far
in our paper are vertex-transitive. Thus, in this section, 
in the context of vertex-transitive graphs,
we will only consider $(k;g_1,\ldots,g_s;N)$-graphs.
In view of the vertex-transitive constructions in \cite{nedsko,jajsir-cage,exojajsir},
it is interesting to ask whether we may be able to construct a vertex-transitive
$(k;g_1,g_2,\ldots,g_s;N)$-graph for any parameter set 
$(k;g_1,g_2,\ldots,g_s;N)$.
To answer this question, we present a negative result that shows that for certain 
parameter sets there exist no vertex-transitive graphs.

\begin{lemma}
If $g_1>3$ is odd, $g_2=2g_1$, and $g_1+g_2=3g_1 < N $,
then there is no vertex-transitive $(3;g_1,g_2;N)$-graph.
\end{lemma}
\begin{proof}
Due to their high level of symmetry, vertex-transitive graphs have the same 
cycle structure through each vertex of the graph. 
Thus, if a trivalent vertex-transitive graph $G$ contains 
a $g_1$- and a $g_2$-cycle, each vertex of $G$ must lie on at least one 
$g_1$- and at least one $g_2$-cycle. Since $G$ is trivalent, this 
means that there exist a $g_1$-cycle ${\cal C}_1$ and $g_2$-cycle ${\cal C}_2$
of $G$ that share at least one edge. Let $P_1,P_2,\ldots,P_r$ be the maximal
subpaths shared by ${\cal C}_1$ and ${\cal C}_2$ of lengths 
$\ell_1,\ell_2, \ldots, \ell_r$, respectively. 

If $r=1$, i.e., the two cycles share just one path, consider the cycle 
constructed from the union of ${\cal C}_1$ and ${\cal C}_2$ with the path
$P_1$ removed. Its length is $g_1+g_2-2\ell_1=3g_1-2\ell_1$, which is an 
odd number smaller than $N$. 
The only admissible odd cycle length smaller than $N$ is $g_1$, and
hence $g_1=3g_1-2\ell_1$ or $0=2g_1-2\ell_1$. But $\ell_1<g_1$, and 
thus $0<2g_1-2\ell_1$. The assumption $r=1$ leads to a contradiction.

If $r>1$, consider the cycles obtained from the union of ${\cal C}_1$
and ${\cal C}_2$ after removing the paths $P_1,P_2,\ldots,P_r$. There is
exactly $r$ of them, say of lengths $g_1,g_2,\ldots,g_r$.
Then $g_1+g_2+\cdots+g_r+2\ell_1+2\ell_2+\cdots+2\ell_r=g_1+g_2=3g_1$,
and since each of the $g_i$'s is either equal to $g_1$ or $2g_1$, and all 
the $\ell_i$'s are $\geq 1$, there cannot be more than $2$ such cycles 
and they both have to be of length $g_1$. This is once again impossible, as 
$g_1+g_1+2\ell_1+2\ell_2=2(g_1+\ell_1+\ell_2)$ is even while $3g_1$ is odd.
\end{proof}

Note that our non-existence result bears further insight 
into the question about the distribution of face lengths in embeddings of Cayley
graphs addressed in \cite{siawat} as well as in the constructions of 
vertex-transitive cages \cite{jajsir-cage,exojajsir}. It appears extremely likely that
there are many further restrictions of the above type, and the classification
of all the parameters sets $(k;g_1,g_2,\ldots,g_s;N)$ that admit the existence
of a vertex-transitive $(k;g_1,g_2,\ldots,g_s;N)$-graph may prove to be very
interesting (and complicated). 

\section{Smallest order $(k_1,\dots,k_t;g_1,\dots,g_s;N)$-graphs}

As mentioned in the introduction,
a $k$-regular graph with girth $g$ of the smallest possible order is called 
a $(k,g)$-cage; we denote the order of a $(k,g)$-cage by $n(k,g)$. 
Following this terminology, we refer to a
$(k_1,\ldots,k_t;g_1,\ldots,g_s;N)$-graph of the smallest possible order
as a {\em $(k_1,\ldots,k_t;g_1,\ldots,g_s;N)$-cage} and denote its order by 
$n(k_1,\ldots,k_t;g_1,\ldots,g_s, N)$. 
Using a simple computer program written in {\em C} (which checks for the presence of cycles
of various lengths in a given graph) and the graph generator \emph{geng} by B.\ D.\ McKay~\cite{nauty},
we have been able to determine the values
of $n(3;g_1,g_2,\ldots,g_s;N)$ and $n(2,3;g_1,g_2,\ldots,g_s;N)$
for all possible combinations of cycle lengths and 
$N = 4,5,\dots,8$.
The results of our calculations are included in 
Tables~\ref{tab:smallestN45}--\ref{tab:smallestk23N8}.

\begin{table}[htb]
\begin{minipage}[t]{0.5\linewidth}
\centering
\begin{tabular}[t]{ll}
\hline
$(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order\\
\hline
$(3;;4)$       & $6$ \\
$(3;3;4)$      & $4$ \\
\hline
\end{tabular}
\end{minipage}%
\begin{minipage}[t]{0.5\linewidth}
\centering
\begin{tabular}[t]{ll}
\hline
$(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order\\
\hline
$(3;;5)$       & $10$ \\
$(3;3;5)$      & $10$ \\
$(3;4;5)$      & $6$ \\
$(3;3,4;5)$    & $4$ \\
\hline
\end{tabular}
\end{minipage} 
\caption{Orders of the smallest $(3;g_1,g_2,\dots,g_s;4)$-graphs (left) and
$(3;g_1,g_2,\dots,g_s;5)$-graphs (right) for all possible combinations. All of them are connected.}
\label{tab:smallestN45}
\end{table}

\begin{table}[htb]
\centering
\begin{tabular}{ll||ll}
\hline
$(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order & $(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order\\

\hline
$(3;;6)$       & $14$ & $(3;3,4;6)$    & $4$  \\
$(3;3;6)$      & $12$ & $(3;3,5;6)$    & $10$ \\
$(3;4;6)$      & $6$  & $(3;4,5;6)$    & $8$  \\
$(3;5;6)$      & $10$ & $(3;3,4,5;6)$  & $6$  \\
\hline
\end{tabular}
\caption{Orders of the smallest $(3;g_1,g_2,\dots,g_s;6)$-graphs for all possible combinations. 
All these graphs are connected.}
\label{tab:smallestN6}
\end{table}

\begin{table}[htb]
\centering
\begin{tabular}{ll||ll}
\hline
$(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order & $(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order\\

\hline
$(3;;7)       $ & $24$ & $(3;4,5;7)    $ & $12$ \\
$(3;3;7)      $ & $16$ & $(3;4,6;7)    $ & $6 $ \\
$(3;4;7)      $ & $16$ & $(3;5,6;7)    $ & $10$ \\
$(3;5;7)      $ & $18$ & $(3;3,4,5;7)  $ & $10$ \\
$(3;6;7)      $ & $14$ & $(3;3,4,6;7)  $ & $8 $ \\
$(3;3,4;7)    $ & $4 $ & $(3;3,5,6;7)  $ & $10$ \\
$(3;3,5;7)    $ & $20$ & $(3;4,5,6;7)  $ & $8 $ \\
$(3;3,6;7)    $ & $12$ & $(3;3,4,5,6;7)$ & $6 $ \\
\hline
\end{tabular}
\caption{Orders of the smallest $(3;g_1,g_2,\dots,g_s;7)$-graphs for all possible combinations.
All these graphs are connected.}
\label{tab:smallestN7}
\end{table}


\begin{table}[htb]
\centering
\begin{tabular}{ll||ll}
\hline
$(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order & $(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order\\

\hline
$(3;;8)   $      & $30$ &   $(3;3,4,5;8)$& $10$   \\
$(3;3;8)  $      & $18$ &   $(3;3,4,6;8)$& $10$ \\
$(3;4;8)  $      & $18$ &   $(3;3,4,7;8)$& $14$ \\
$(3;5;8)  $      & $20$ &   $(3;3,5,6;8)$& $20$ \\
$(3;6;8)  $      & $14$ &   $(3;3,5,7;8)$& $20$ \\
$(3;7;8)  $      & $24$ &   $(3;3,6,7;8)$& $12$   \\
$(3;3,4;8)$      & $4$ &    $(3;4,5,6;8)$& $16$ \\
$(3;3,5;8)$      & $26^*$ &   $(3;4,5,7;8)$& $12$ \\
$(3;3,6;8)$      & $22$ &   $(3;4,6,7;8)$& $12$ \\
$(3;3,7;8)$      & $16$ &   $(3;5,6,7;8)$& $12$ \\
$(3;4,5;8)$      & $18$ &   $(3;3,4,5,6;8)$& $6$ \\
$(3;4,6;8)$      & $6$ &    $(3;3,4,5,7;8)$& $14$ \\
$(3;4,7;8)$      & $16$ &   $(3;3,4,6,7;8)$& $8$ \\
$(3;5,6;8)$      & $10$ &   $(3;3,5,6,7;8)$& $10$ \\
$(3;5,7;8)$      & $18$ &   $(3;4,5,6,7;8)$& $8$ \\
$(3;6,7;8)$      & $18$ &   $(3;3,4,5,6,7;8)$& $8$ \\
\hline
\end{tabular}
\caption{Orders of the smallest $(3;g_1,g_2,\dots,g_s;8)$-graphs for all possible combinations. All graphs
are connected except of the smallest $(3;3,4,6;8)$-graph which is the union of $K_4$ and $K_{3,3}$. In case of 
the smallest $(3;4,5,6;8)$-graph there exist both a connected and a disconnected graph of order $16$.
The $(3;3,5;8)$-graph was found by G. Exoo.}
\label{tab:smallestN8}
\end{table}

\begin{table}[htb]
\begin{minipage}[t]{0.5\linewidth}
\centering
\begin{tabular}[t]{ll}
\hline
$(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order\\
\hline
$(2,3;;4)$       & $5$ \\
$(2,3;3;4)$      & $4$ \\
\hline
\end{tabular}
\end{minipage}%
\begin{minipage}[t]{0.5\linewidth}
\centering
\begin{tabular}[t]{ll}
\hline
$(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order\\
\hline
$(2,3;;5)$       & $7$ \\
$(2,3;3;5)$      & $6$ \\
$(2,3;4;5)$      & $5$ \\
$(2,3;3,4;5)$    & $4$ \\
\hline
\end{tabular}
\end{minipage} 
\caption{Orders of the smallest $(2,3;g_1,\dots,g_s;4)$-graphs (left) and
$(2,3;g_1,\dots,g_s;5)$-graphs (right) for all possible combinations. All of them are connected.}
\label{tab:smallestk23N45}
\end{table}

\begin{table}[htb]
\centering
\begin{tabular}{ll||ll}
\hline
$(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order & $(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order\\

\hline
$(2,3;;6)$       & $8$ & $(2,3;3,4;6)$    & $4$  \\
$(2,3;3;6)$      & $6$ & $(2,3;3,5;6)$    & $6$ \\
$(2,3;4;6)$      & $5$ & $(2,3;4,5;6)$    & $6$  \\
$(2,3;5;6)$      & $7$ & $(2,3;3,4,5;6)$  & $5$  \\
\hline
\end{tabular}
\caption{Orders of the smallest $(2,3;g_1,\dots,g_s;6)$-graphs for all possible combinations. 
All these graphs are connected.}
\label{tab:smallestk23N6}
\end{table}

\begin{table}[htb]
\centering
\begin{tabular}{ll||ll}
\hline
$(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order & $(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order\\

\hline
$(2,3;;7)       $ & $10$& $(2,3;4,5;7)    $ & $6$ \\
$(2,3;3;7)      $ & $6$ & $(2,3;4,6;7)    $ & $6$ \\
$(2,3;4;7)      $ & $5$ & $(2,3;5,6;7)    $ & $7$ \\
$(2,3;5;7)      $ & $8$ & $(2,3;3,4,5;7)  $ & $5$ \\
$(2,3;6;7)      $ & $8$ & $(2,3;3,4,6;7)  $ & $7$ \\
$(2,3;3,4;7)    $ & $4$ & $(2,3;3,5,6;7)  $ & $6$ \\
$(2,3;3,5;7)    $ & $8$ & $(2,3;4,5,6;7)  $ & $7$ \\
$(2,3;3,6;7)    $ & $7$ & $(2,3;3,4,5,6;7)$ & $6$ \\
\hline
\end{tabular}
\caption{Orders of the smallest $(2,3;g_1,\ldots,g_s;7)$-graphs for all possible combinations.
All these graphs are connected.}
\label{tab:smallestk23N7}
\end{table}

\begin{table}[htb]
\centering
\begin{tabular}{ll||ll}
\hline
$(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order & $(k_1,\dots,k_t;g_1,\ldots,g_s;N)$ & order\\

\hline
$(2,3;;8)   $      & $11$ &   $(2,3;3,4,5;8)$&    $5 $ \\  %  1    17
$(2,3;3;8)  $      & $6 $ &   $(2,3;3,4,6;8)$&    $9 $\\  %  2    18
$(2,3;4;8)  $      & $5 $ &   $(2,3;3,4,7;8)$&    $8 $ \\  %  3    19
$(2,3;5;8)  $      & $8 $ &   $(2,3;3,5,6;8)$&    $6 $ \\  %  4    20
$(2,3;6;8)  $      & $8 $ &   $(2,3;3,5,7;8)$&    $10$ \\  %  5    21
$(2,3;7;8)  $      & $10$ &   $(2,3;3,6,7;8)$&    $7 $ \\  %  6    22
$(2,3;3,4;8)$      & $4 $ &   $(2,3;4,5,6;8)$&    $9 $ \\  %  7    23
$(2,3;3,5;8)$      & $8 $ &   $(2,3;4,5,7;8)$&    $7 $ \\  %  8    24
$(2,3;3,6;8)$      & $9 $ &   $(2,3;4,6,7;8)$&    $9 $ \\  %  9    25
$(2,3;3,7;8)$      & $8 $ &   $(2,3;5,6,7;8)$&    $8 $ \\  %  10   26
$(2,3;4,5;8)$      & $6 $ &   $(2,3;3,4,5,6;8)$&  $6 $ \\  %  11   27
$(2,3;4,6;8)$      & $6 $ &   $(2,3;3,4,5,7;8)$&  $8 $ \\  %  12   28
$(2,3;4,7;8)$      & $8 $ &   $(2,3;3,4,6,7;8)$&  $7 $ \\  %  13   29
$(2,3;5,6;8)$      & $7 $ &   $(2,3;3,5,6,7;8)$&  $7 $ \\  %  14   30
$(2,3;5,7;8)$      & $9 $ &   $(2,3;4,5,6,7;8)$&  $7 $ \\  %  15   31
$(2,3;6,7;8)$      & $9 $ &   $(2,3;3,4,5,6,7;8)$&$7 $ \\  %  16   32
\hline
\end{tabular}
\caption{Orders of the smallest $(2,3;g_1,\ldots,g_s;8)$-graphs for all possible combinations. All graphs
are connected. Note that in case of the smallest $(2,3;3,4,6;8)$-graph there 
exist both a connected and a disconnected graph of order $9$.}
\label{tab:smallestk23N8}
\end{table}

Furthermore,
it is not hard to see that for all $2 \leq k$ and $3 \leq g $
\[ n(k;g;g+1) = n(k,g), \]
and for all $2 \leq k$ and $3 \leq g_1 < \cdots < g_s < N$,
\[ n(k,g_1) \leq n(k;g_1,\ldots,g_s;N), \]
as the class of the $(k;g_1,\ldots,g_s;N)$-graphs is a subclass of the class of the
$(k,g)$-graphs. 

The following well-known {\em Moore bound} \cite{exojaj}
serves therefore as a lower bound for
$n(k; g_1,g_2,\ldots,g_s;N) $ as well.


\begin{equation} \label{moore1}
n(k,g) \ge  \left\{ 
\begin{array}{lc} 1 + k + k(k-1) + \dots + k(k-1)^{(g-3)/2}, & g \mbox{ odd } \\
                              2(1 + (k-1) + \dots + (k-1)^{(g-2)/2}), & g \mbox{ even } 
\end{array}
\right.
\end{equation}
A $(k,g)$-graph of order equal to the Moore bound is called a {\em Moore
graph} and Moore graphs are known to exist (even though only for very special sets of
parameters \cite{exojaj}). Thus, there are instances of our generalized problem where
the Moore bound is actually achieved. Namely, the Moore bound is at least achieved for any
set of parameters $(k;g;g+1)$ for which a $(k,g)$-Moore graph exists.

The general situation is however quite different, and it appears likely that the `trivial' cases are the only cases where the order of a generalized cage matches the order of the corresponding cage.
A specific situation supporting our argument is described in the following lemma.

\begin{lemma} \label{lowlarge}
Let $3 \leq k,g$ and suppose that $ N > 2g $. Then\\[-8mm]
\begin{multline}
n(k;g;N) \ge\\  \left\{ 
\begin{array}{lc} g(1 + (k-2) + (k-2)(k-1) + \dots + (k-2)(k-1)^{(g-3)/2}), 
& g \mbox{ odd,} \\
                  g(1 + (k-2) + (k-2)(k-1) + \dots + (k-2)(k-1)^{(g-2)/2}), 
& g \mbox{ even.} 
\end{array}
\right.
\end{multline}
\end{lemma}

\begin{proof}
Let $k,g$ and $N$ be as above and suppose first that $g$ is odd. By definition,
any $(k;g;N)$-graph $G$ contains at least one $g$-cycle. Observe that no two $g$-cycles 
in such a graph can share an edge as such an occurrence would lead to the existence
of $g'$-cycle of length strictly between $g$ and $N$. Let ${\cal C}$ be a $g$-cycle
of $G$, assume that the vertices of ${\cal C}$ are the vertices $v_1,v_2, \ldots,
v_g$, and consider the $g(k-2)$ edges incident to the vertices $v_i$ not included
in ${\cal C}$. We claim that each $v_i$ is attached to a separate `tree' of 
$(k-2) + (k-2)(k-1) + \dots + (k-2)(k-1)^{(g-3)/2}$ vertices (with any two trees
mutually disjoint).
The argument is similar to the argument used to prove the Moore bound. Consider the 
end-points of the $(k-2)$ edges adjacent to $v_i$ and not belonging to ${\cal C}$.
Each of these must be adjacent to $k-1$ new vertices not shared with any other branch 
of the tree at $v_i$ and neither with any other tree rooted at $v_j$, $j \neq i$. 
This is due to the fact that we cannot create shorter cycles than $g$ and cannot 
even create
cycles of length $g$ that would share a part of ${\cal C}$. The first time an edge
from a tree from $v_i$ can go to another branch of that tree or to one of the other
trees is at the distance $(g-1)/2$ from $v_i$. This completes the proof for odd
$g$. 

The case for even $g$ differs from the odd case in that there might exist two 
cycles of length $g$ that share at least an edge. More precisely, if $g=2m$,
there might exist two $g$-cycles that share an $m$-path.
If no such two $g$-cycles exist in $G$, a very similar proof to the odd case shows
the bound stated. If $G$ contains two $g$-cycles sharing an $m$-path, trees attached
to vertices antipodal with respect to these cycles (i.e., lying on the same cycle and of distance
$m$) may form another $m$-path and thus the attached trees may share vertices. 
It is not hard to see, however, that this is not possible. Namely, if there existed
two distinct vertices anywhere on these two $g$-cycles that were joined by an additional
path of length $m$, one could always construct a cycle involving this path and parts
of the original $g$-cycles of length smaller than $2g$ but not equal to $g$.
Thus, all the trees attached to the $3m$ vertices of the two $g$-cycles must be disjoint 
in this case as well, and the number of vertices of the graph $G$ must be at least 
$3m(1 + (k-2) + (k-2)(k-1) + \dots + (k-2)(k-1)^{(g-2)/2})$. 
\end{proof}

Two upper bounds follow from the proof of Corollary~\ref{disc}:
\[ n(k;g_1,\ldots,g_s;N) \leq \sum_{i=1}^s n(k;g_i;N), \]
\[ n(k_1,\ldots,k_t;g_1,\ldots,g_s;N) \leq \sum_{i=1}^t \sum_{j=1}^s n(k_i;g_j;N), \]
where the second bound could clearly be improved. Both upper bounds are obtained
by considering disconnected graphs which yields another
interesting aspect of the problem of the minimal order of an 
$(k;g_1, g_2,\ldots,g_s;N)$-graph that does not occur with regard to $(k,g)$-cages:
the order $n(k; g_1,g_2,\ldots,g_s;N)$ can be achieved by a disconnected union 
of smaller graphs (as is the case for $k=2$).  
The smallest such example for $k = 3$ is the $(3;3,4,6;8)$-cage which turns out to be a
union of the complete graph $K_4$, the smallest $(3;3,4;8)$-graph, 
and the complete bipartite graph 
$K_{3,3}$, the smallest $(3;4,6;8)$-graph. It has order $10$ while the smallest
connected $(3;3,4,6;8)$-graph has order $14$. It is also possible that 
$n(k;g_1,g_2,\ldots,g_s;N)$ is achieved by both a connected and a disconnected graph. 
The smallest case for $k = 3$ is $n(3;4,5,6;8)$: there exist connected and disconnected 
$(3;4,5,6;8)$-graphs of order $16$ which is the smallest value for this set of parameters.
On the other hand, there exists 
an infinite family of triples $(g_i,g'_i;N_i)$, $g_i < g'_i< N_i$ and $ k \geq 3 $, 
such that 
\[ n(k;g_i,g'_i;N_i) < n(k;g_i;N_i) + n(k;g'_i;N_i), \]
and the corresponding generalized cage is connected. 
A somewhat disappointing example of this 
situation can be obtained as follows:
\[ n(3;3,4;N) = 4 < n(3;3;N) + n(3;4;N), \]
where $N$ is assumed to be $ > 4 $. 
At this point, we do not have a more meaningful example of this situation.

One of the fundamental problems when trying to determine a precise value of 
$n(k,g)$ (the order of the smallest $(k,g)$-graph) is that beside having to 
construct a graph of order $n(k,g)$, one also
has to establish the non-existence of a smaller $(k,g)$-graph. 
Although obviously one is to expect the
same problem to occur with regard to our generalized cages, 
there are certain parameter sets where
establishing the non-existence of smaller graphs of those parameters proves out to be a 
bit less demanding. 
One such example are the sets of parameters with $k=3$ and the required cycle lengths 
covering the whole range of cycle lengths from the girth $3$ through $N-1$ -- 
the $(3;3,4,\dots,N-1;N)$-cages.
These are depicted in Figure~\ref{fig:simplecages} for $N \geq 4$ and it is easy 
to see that the graphs $G_N$ have cycles of all the lengths 
$3,4,\dots,N-1$ while being of the smallest possible orders ($N$ for $N$ even
and $N-1$ for $N$ odd) -- due to the fact that they must contain an $N-1$ cycle.
These graphs can be thought of as in some sense opposite to the graphs 
considered in Lemma~\ref{lowlarge}. 

\begin{figure} %\label{fig:simplecages}
\centering
\begin{tikzpicture}
\draw (0,0)--(1,1);
\draw (1,1)--(1,-1);
\draw (1,1)--(2,0);
\draw (0,0)--(2,0);
\draw (0,0)--(1,-1);
\draw (1,-1)--(2,0);
\fill [color=black] (0,0) circle (1.5pt);
\fill [color=black] (1,1) circle (1.5pt);
\fill [color=black] (1,-1) circle (1.5pt);
\fill [color=black] (2,0) circle (1.5pt);
\draw (1,-1.2) node[below] {$G_4 = G_5$};
\end{tikzpicture} \hfil
\begin{tikzpicture}
\draw (0,0)--(1,1);
\draw (1,1)--(1,-1);
\draw (1,1)--(2,1);
\draw (0,0)--(3,0);
\draw (0,0)--(1,-1);
\draw (1,-1)--(2,-1);
\draw (2,1)--(3,0);
\draw (2,-1)--(3,0);
\draw (2,-1)--(2,1);
\fill [color=black] (0,0) circle (1.5pt);
\fill [color=black] (1,1) circle (1.5pt);
\fill [color=black] (1,-1) circle (1.5pt);
\fill [color=black] (2,1) circle (1.5pt);
\fill [color=black] (2,-1) circle (1.5pt);
\fill [color=black] (3,0) circle (1.5pt);
\draw (1.5,-1.2) node[below] {$G_6 = G_7$};
\end{tikzpicture} \hfil
\begin{tikzpicture}
\draw (0,0)--(1,1);
\draw (1,1)--(1,-1);
\draw (1,1)--(2,1);
\draw (0,0)--(4,0);
\draw (0,0)--(1,-1);
\draw (1,-1)--(2,-1);
\draw [dashed](2,1)--(3,1);
\draw (2,1)--(2,-1);
\draw [dashed](2,-1)--(3,-1);
\draw (3,-1)--(4,0);
\draw (3,1)--(4,0);
\draw (3,1)--(3,-1);
\fill [color=black] (0,0) circle (1.5pt);
\fill [color=black] (1,1) circle (1.5pt);
\fill [color=black] (1,-1) circle (1.5pt);
\fill [color=black] (2,1) circle (1.5pt);
\fill [color=black] (2,-1) circle (1.5pt);
\fill [color=black] (3,1) circle (1.5pt);
\fill [color=black] (3,-1) circle (1.5pt);
\fill [color=black] (4,0) circle (1.5pt);
\draw (2,-1.2) node[below] {$G_N = G_{N+1}$, $N$ even};
\end{tikzpicture}

\caption{Smallest $(3;3,4,\dots,N-1;N)$-graphs $G_N$, $N \geq 4$.} 
\label{fig:simplecages}
\end{figure}

To conclude our paper, we point out that the above cages are not unique with
respect their parameters. It is easy to see that the graph depicted in 
Figure~\ref{fig:counter} is also a $(3;3,4,5,6,7,8;9)$-graph but it is not isomorphic
to the graph $G_8=G_9$.

\begin{figure} %\label{fig:counter}
\centering
\begin{tikzpicture}
\draw (0,0)--(1,1);
\draw (1,1)--(1,-1);
\draw (1,1)--(2,1);
\draw (0,0)--(4,0);
\draw (0,0)--(1,-1);
\draw (1,-1)--(2,-1);
\draw (2,1)--(3,1);
\draw (2,1)--(3,-1);
\draw (2,-1)--(3,1);
\draw (2,-1)--(3,-1);
\draw (3,-1)--(4,0);
\draw (3,1)--(4,0);
\fill [color=black] (0,0) circle (1.5pt);
\fill [color=black] (1,1) circle (1.5pt);
\fill [color=black] (1,-1) circle (1.5pt);
\fill [color=black] (2,1) circle (1.5pt);
\fill [color=black] (2,-1) circle (1.5pt);
\fill [color=black] (3,1) circle (1.5pt);
\fill [color=black] (3,-1) circle (1.5pt);
\fill [color=black] (4,0) circle (1.5pt);
\end{tikzpicture}

\caption{Smallest $(3;3,4,5,6,7,8;9)$-graph not isomorphic to  $G_8 = G_9$.} 
\label{fig:counter}
\end{figure}

%\vskip 5mm

%\begin{table}
%\centering
%\begin{tabular}{lll}
%\hline
%$(k,N;g_1,g_2,\ldots,g_s)$.\ & order & comment \\
%
%\hline
%$(3,11;)$       & $\boldsymbol{126}$ & $(3,12)$-cage \\ 
%$(3,11;10)$     & $\boldsymbol{70}$  & $(3,10)$-cage \\ 
%$(3,11;8)$      & $54$ &  \\ 
%$(3,11;8,10)$   & $\boldsymbol{30}$ & $(3,8)$-cage, Tutte's 8-cage  \\ 
%$(3,11;6,8)$    & $162$ &  \\ 
%$(3,11;6,10)$   & $42$ &  \\ 
%$(3,11;6,8)$    & $90$ & \\
%$(3,11;6,8,10)$ & $\boldsymbol{14}$ & $(3,6)$-cage, Heawood graph \\
%\hline
%\end{tabular}
%\caption{A list of the smallest known (bipartite) $(3,11;g_1,g_2,\dots,g_s)$-graphs for all 
%possible $g_i$. If a order is printed in bold then such graph is the smallest of its kind.}
%
%\label{tab:smallest}
%\end{table}

%\newpage

%\clearpage

\begin{thebibliography}{10}

\bibitem{par&al}
G. Araujo-Pardo, C. Balbuena, P. Garc\' \i a-V\' azquez, X. Marcote and J.C. Valenzuela,
 \newblock On the order of $(\{r,m\};g)$-cages of even girth,  \newblock 
\emph{Discrete Math.} 308, No. 12 (2008), 2484--2491.

\bibitem{bal&al}
C. Balbuena, T. Jiang, Y. Lin, X. Marcote, and M. Miller,  \newblock 
A lower bound on the order of regular graphs with given girth pair, \newblock 
\emph{J. Graph Theory} 55, No. 2 (2007), 153--163.

\bibitem{balmar}
C. Balbuena, X. Marcote,  \newblock Monotonocity of the order of $(D; g)$-cages, 
 \newblock \emph{Appl. Math. Lett.} 24 No. 11 (2011), 1933--1937.

\bibitem{bobgru&pis}
M. Boben, B. Gr\" unbaum and T. Pisanski, \newblock 
Multilaterals in configurations,  \newblock 
\emph{Beitr. Algebra Geom.} 54, No. 1 (2013), 263--275.
%Beitr\" age zur Algebra und Geometrie, 
%DOI 10.1007/s13366-011-0065-3.

\bibitem{cam}
C.M. Campbell,  \newblock 
On cages on girth pair $(6,b)$,  \newblock 
\emph{Discrete Math.} 177 (1997), 259--266.

\bibitem{chagou&kap}
G. Chartrand, R.J. Gould, S.F. Kapoor, \newblock 
Graphs with prescribed degree sets and girth, \newblock 
\emph{Periodica Mathematica Hungarica} \textbf{12} (1981), 261--266.

\bibitem{erdossachs}
P. Erd\H{o}s and H. Sachs, \newblock 
Regul\" are Graphen gegebener Taillenweite mit minimaler Knotenzahl, \newblock 
\emph{Wiss. Z. Uni. Halle (Math. Nat.)} \textbf{12} (1963), 251--257.

\bibitem{exojaj}
G. Exoo and R. Jajcay,  \newblock 
Dynamic cage survey, \newblock 
\emph{Electron. J. Combin.}, Dynamic Survey 16, September 2008.

\bibitem{exojajsir}
G. Exoo, R. Jajcay and J. \v Sir\' a\v n, \newblock 
Cayley cages, \newblock 
\emph{J. Algebr. Comb.} 38, 1 (2013), 209--224. 

\bibitem{fur&al}
Z. F\" uredi, F. Lazebnik, \' A. Seress, V.A. Ustimenko and A. J. Woldar,  \newblock 
Graphs with prescribed girth and bi-degree,   \newblock 
\emph{J. Combin. Th. (B)} 64 (1995), 228--239.

\bibitem{grotuc}
J. L. Gross and T. W. Tucker,  \newblock 
\emph{Topological graph theory},  \newblock Dover Publications, 2001.

\bibitem{grunbaum}
B. Gr\"{u}nbaum, \emph{Configurations of Points and Lines},   \newblock 
Graduate Studies in Mathematics, 103,  \newblock 
American Mathematical Society, Providence, RI, 2009.

\bibitem{har&kov1}
F. Harary and P. Kov\' acs, \newblock 
Regular graphs with given girth pair, \newblock 
\emph{J. Graph Theory} 7 (1983), 209--218.

\bibitem{har&kov2}
F. Harary and P. Kov\' acs, \newblock 
The smallest graphs with prescribed odd and even girth, \newblock 
\emph{Caribb. J. Math.} 1 (1982), 24--26.

\bibitem{jajsir-cage}
R. Jajcay and J. \v Sir\' a\v n,  \newblock 
Small vertex-transitive graphs of given degree and girth,  \newblock 
\emph{Ars Mathematica Contemporanea} 4 (2011), 375--384.

\bibitem{jia}
T. Jiang,  \newblock 
Short even cycles in cages with odd girth, \newblock 
\emph{Ars Comb.} 59 (2001), 
165--169.

\bibitem{lazustwol2}
F. Lazebnik, V. A. Ustimenko, and A. J. Woldar, \newblock 
New upper bounds on the order of cages, \newblock 
\emph{Electron. J. Combin.} \textbf{4} (1997), \#13.

\bibitem{nauty}
B. D. McKay,  \newblock nauty package, \url{http://cs.anu.edu.au/~bdm/nauty/}.

\bibitem{nedsko}
R. Nedela and M. \v Skoviera,  \newblock 
Regular maps on surfaces with large planar width,  \newblock 
\emph{European J. Combin.} \textbf{22} (2001), 243--261.

\bibitem{pbmog}
T. Pisanski, M. Boben, D. Maru\v{s}i\v{c}, A. Orbani\'{c}, A. Graovac, \newblock 
The 10-cages and derived configurations, \newblock 
\emph{Discrete Math.} \textbf{275} (2004), 265--276.

\bibitem{reivad&wig}
O. Reingold, S. Vadhan, and A. Wigderson,  \newblock 
Entropy waves, the zig-zag
graph product, and new constant-degree expanders,  \newblock 
\emph{Ann. of Math. (2)}
\textbf{155} (2002), 157--187.

\bibitem{sachs}
H. Sachs, \newblock 
Regular graphs with given girth and restricted circuits, \newblock 
\emph{J. London Math. Soc.} \textbf{38} (1963), 423--429.

\bibitem{siawat}
J. \v Siagiov\' a and M. E. Watkins,  \newblock 
Covalence sequences of planar vertex-homogeneous maps, \newblock 
\emph{Discrete Math.} \textbf{307} (2007), 599--614.

\bibitem{xuwan&wan}
B.-G. Xu, P. Wang, J.-F. Wang,  \newblock 
On the monotonicity of $(k; g, h)$-graphs, \newblock 
\emph{Acta Math. Appl. Sin.}, Engl. Ser. 18, No.3 (2002), 477--480.

\end{thebibliography}
\end{document}