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

A connected 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. Since its introduction by Plummer in the 1980s, this combinatorial parameter has been studied for many classes of interesting graphs. In 2005, Brouwer and Haemers proved that every distance-regular graph of even order is 1 -extendable and in 2014, Cioabă and Li showed that any connected strongly regular graph of even order is 3-extendable except for a small number of exceptions. In this paper, we extend and generalize these results. We prove that all distance-regular graphs with diameter D ≥ 3 are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency k ≥ 3 that depend on k , λ and μ , where λ is the number of common neighbors of any two adjacent vertices and μ is the number of common neighbors of any two vertices in distance two. In many situations, we show that the extendability of a distance-regular graph with valency k grows linearly in k . We conjecture that the extendability of a distance-regular graph of even order and valency k is at least ⌈ k / 2 ⌉ − 1 and we prove this fact for bipartite distance-regular graphs. In course of this investigation, we obtain some new bounds for the max-cut and the independence number of distance-regular graphs in terms of their size and odd girth and we prove that our inequalities are incomparable with known eigenvalue bounds for these combinatorial parameters. [ABSTRACT FROM AUTHOR]