For $3 \le k \le 20$ with $k \ne 4,8,12$, all the smallest currently known $k$--regular graphs of girth $5$ have the same orders as the girth $5$ graphs obtained by the following construction: take a (not necessarily Desarguesian) elliptic semiplane $\cal S$ of order $n-1$ where $n = k - r$ for some $r \ge 1$; the Levi graph $\varGamma({\cal S})$ of $\cal S$ is an $n$--regular graph of girth $6$; parallel classes of $\cal S$ induce co--cliques in $\varGamma({\cal S})$, some of which are eventually deleted; the remaining co--cliques are amalgamated with suitable $r$--regular graphs of girth at least $5$. For $k > 20$, this construction yields some new instances underbidding the smallest orders known so far.
Girth 5 Graphs from Elliptic Semiplanes
FUNK, Martin
2009-01-01
Abstract
For $3 \le k \le 20$ with $k \ne 4,8,12$, all the smallest currently known $k$--regular graphs of girth $5$ have the same orders as the girth $5$ graphs obtained by the following construction: take a (not necessarily Desarguesian) elliptic semiplane $\cal S$ of order $n-1$ where $n = k - r$ for some $r \ge 1$; the Levi graph $\varGamma({\cal S})$ of $\cal S$ is an $n$--regular graph of girth $6$; parallel classes of $\cal S$ induce co--cliques in $\varGamma({\cal S})$, some of which are eventually deleted; the remaining co--cliques are amalgamated with suitable $r$--regular graphs of girth at least $5$. For $k > 20$, this construction yields some new instances underbidding the smallest orders known so far.File | Dimensione | Formato | |
---|---|---|---|
G5GfES.pdf
non disponibili
Tipologia:
Documento in Pre-print
Licenza:
DRM non definito
Dimensione
211.26 kB
Formato
Adobe PDF
|
211.26 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.