RESEARCH ARTICLE

Exact values of girth for some graphs $D(k,q)$ and upper bounds of the order of cage

Piotr Pikuta

Institute of Mathematics, Maria Curie-Skłodowska University, pl. Marii Curie-Skłodowskiej 1, 20–031 Lublin, Poland

Abstract: Let $q$ be a prime power and $k\in\left\{5,7,9,11\right\}$. In this paper it is shown that the girth of a graph $D\left(k,q\right)$ is equal to $k+5$. As a consequence, explicit examples of graphs which provide the best known upper bounds of the order of $\left(r,g\right)$-cages, $r\geq 5$, $g\in\left\{10,14,16\right\}$, are given.

Keywords: Girth, Cages, Extremal.

MSC: 05C35, 05C38

Received: 09.06.2008
Revised: 09.06.2008

Language: English

Bibliographic databases:

• 
•