The Classification of $2$-Extendable Edge-Regular Graphs with Diameter $2$

  • Klavdija Kutnar
  • Dragan Marušič
  • Štefko Miklavič
  • Primož Šparl

Abstract

Let $\ell$ denote a non-negative integer. A connected graph $\Gamma$ of even order at least $2\ell+2$ is $\ell$-extendable if it contains a matching of size $\ell$ and if every such matching is contained in a perfect matching of $\G$. A connected regular graph $\Gamma$ is edge-regular, if there exists an integer $\lambda$ such that every pair of adjacent vertices of $\Gamma$ have exactly $\lambda$  common neighbours. In this paper we classify $2$-extendable edge-regular graphs of even order and diameter $2$.

Published
2019-02-08
Article Number
P1.16