×

\((D;4)\)-cages: Some new results. (English) Zbl 0913.05066

Let \(D\) be a set of positive integers. A \((D;g)\)-cage is a graph with degree set \(D\) and girth \(g\), with the least possible number \(f(D;g)\) of vertices. (For \(D=\{k\}\) one obtains the usual notion of a \((k,g)\)-cage.) It is shown that for some pairs \((D;4)\) there are only non-bipartite cages, while for others both bipartite and non-bipartite cages exist. The value of \(f(D;4)\) is explictly computed for each three-element set \(D\), provided that max \(D\leq 10\). Furthermore, it is proved that \(f(D;6)=25\) for \(D=\{3,4,6\}\).

MSC:

05C38 Paths and cycles

Keywords:

degree set; girth; cages