Max-cut and extendability of matchings in distance-regular graphs |
| |
Institution: | 1. Department of Mathematical Sciences, University of Delaware, Newark, DE 19716-2553, USA;2. Wu Wen-Tsun Key Laboratory of Mathematics of CAS, School of Mathematical Sciences, University of Science and Technology of China, 96 Jinzhai Road, Hefei, 230026, Anhui, PR China |
| |
Abstract: | A connected graph of even order is called -extendable if it contains a perfect matching, and any matching of edges is contained in some perfect matching. The extendability of is the maximum such that is -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 -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 are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency that depend on , 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 grows linearly in . We conjecture that the extendability of a distance-regular graph of even order and valency is at least 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|