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)$.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.