Independence number in n-extendable graphs

AbstractLet G be a connected graph with p vertices and n a positive integer with 1 ⩽ n ⩽ (p/2) − 1. G is said to be 0-extendable if G has a perfect matching. G is said to be n-extendable if G has a matching of size n and every matching of size n in G extends to (i.e. is a subset of) a perfect matching. It is shown that in every nonbipartite, n-extendable graph G the independence number α(G) satisfies α(G)⩽(p/2) − n and that this upper bound is sharp for all n and p. If G is a nonbipartite, n-extendable graph with 4n + 2 ⩾ p, then G is Hamiltonian, and if 4n ⩾ p + 2k, then G is (n + 2 + k)-connected for all integers k ⩾ 0. Furthermore, the saturation number s(G) of a graph G is defined to be the smallest cardinality of a maximal matching of G. Some relations between the parameters s(G) and α(G) in n-extendable graphs G of order p are presented