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.
2009
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11563/18627
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact