Amply regular graphs with parameters $(\nu,k,1,1)$ can be characterized as regular graphs of order $\nu$ and valency $k$ such that every edge lies in some 3-cycle, but in no 4-cycle. Such graphs can exist only if $k \equiv 0$ (mod $2$) and $\nu k \equiv 0$ (mod $3$). Extremal graph theory provides some further restriction: we conjecture that a lower bound is given by $\nu \ge k^2- 1$ and show that eventually this bound is sharp for even prime powers $k= 2^\kappa$. For $k=4$, there exist connected instances for all feasible orders $\nu\equiv 0$ (mod $2$) with $\nu \ge 15$, e.g. line graphs of generalized Petersen graphs with girth at least $5$. For $k \ge 6$, the existence of instances remains an open problem for many values of $\nu$. We show that $n$ connected amply regular graphs $\Gamma^{(i)}$ with parameters $(\nu^{(i)},2n,1,1)$ can be amalgamated to a connected amply regular graph with parameters $((\sum^n_{i=1} \nu^{(i)}),2n,1,1)$.

On a Class of Amply Regular Graphs

FUNK, Martin
2010-01-01

Abstract

Amply regular graphs with parameters $(\nu,k,1,1)$ can be characterized as regular graphs of order $\nu$ and valency $k$ such that every edge lies in some 3-cycle, but in no 4-cycle. Such graphs can exist only if $k \equiv 0$ (mod $2$) and $\nu k \equiv 0$ (mod $3$). Extremal graph theory provides some further restriction: we conjecture that a lower bound is given by $\nu \ge k^2- 1$ and show that eventually this bound is sharp for even prime powers $k= 2^\kappa$. For $k=4$, there exist connected instances for all feasible orders $\nu\equiv 0$ (mod $2$) with $\nu \ge 15$, e.g. line graphs of generalized Petersen graphs with girth at least $5$. For $k \ge 6$, the existence of instances remains an open problem for many values of $\nu$. We show that $n$ connected amply regular graphs $\Gamma^{(i)}$ with parameters $(\nu^{(i)},2n,1,1)$ can be amalgamated to a connected amply regular graph with parameters $((\sum^n_{i=1} \nu^{(i)}),2n,1,1)$.
2010
File in questo prodotto:
File Dimensione Formato  
CARG1.pdf

non disponibili

Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 231.55 kB
Formato Adobe PDF
231.55 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/18629
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact