Max-cut and extendability of matchings in distance-regular graphs

Abstract

Let $G$ be a distance-regular graph of order $v$ and size $e$. In this paper, we show that the max-cut in $G$ is at most $e(1-1/g)$, where $g$ is the odd girth of $G$. This result implies that the independence number of $G$ is at most $\frac{v}{2}(1-1/g)$. We use this fact to also study the extendability of matchings in distance-regular graphs. A graph $G$ of even order $v$ is called $t$-extendable if it contains a perfect matching, $t<v/2$ and any matching of $t$ edges is contained in some perfect matching. The extendability of $G$ is the maximum $t$ such that $G$ is $t$-extendable. We generalize previous results on strongly regular graphs and show that all distance-regular graphs with diameter $D\ge 3$ are $2$-extendable. We also obtain various lower bounds for the extendability of distance-regular graphs of valency $k$ that depend on $k$, $\lambda$ and $\mu$, where $\lambda$ is the number of common neighbors of any two adjacent vertices and $\mu$ is the number of common neighbors of any two vertices in distance two.

18 pages, accepted to European Journal of Combinatorics

References in corpus (2)

• Distance-regular graphs
• New bounds for the max-$k$-cut and chromatic number of a graph

Cited by in corpus (1)

• Cometric Association Schemes