On minimum degree of strongly \(k\)-extendable graphs (Q2747189)

This paper is a continuation of the paper reviewed above (see Zbl 0983.05068). In the present paper also simple connected graphs \(G\) on \(2n\) vertices with a perfect matching are considered. The main results of the paper are the proof of a necesary condition, in terms of the minimum degree \(\delta(G)\), for \(k^*\)-extendable graphs (Theorem 3.3) and a characterization of \(k^*\)-extendable graphs on \(2n\) vertices for \(k= n-2\) and \(k= n-3\) (Theorems 4.1, 4.3 and 4.4). At first some properties of \(k\)-extendable and \(k^*\)-extendable graphs are summarized (partially proved by the author himself) which are useful for the further investigations. Then the author gets the following necessary condition: If \(G\) is a \(k^*\)-extendable graph on \(2n\) vertices, \(0\leq k\leq n-2\), then \(k+3\leq \delta(G)\leq n-2\) or \(\delta(G)\geq 2k+3\) (Theorem 3.3).NEWLINENEWLINENEWLINEIn connection with this theorem, some corollaries and lemmas he determines the set of realizable values for \(\delta(G)\) of \(k^*\)-extendable graphs and finds that, for any integers \(n\), \(k\) and \(r\) with \(0\leq k\leq n-2\), there exists a \(k^*\)-extendable graph on \(2n\) vertices with \(\delta(G)= r\) if \(r\) is contained in given intervals (Theorem 3.8).NEWLINENEWLINENEWLINEFinally, in Section 4, the above-mentioned graphs are characterized by the following theorems: (1) \(G\) is an \((n-2)^*\)-extendable graph on \(2n\geq 4\) vertices iff \(G\) is the complete graph \(K_{2n}\) (Theorem 4.1). (2) If \(G\) is a graph on \(2n\geq 6\) vertices, then \(G\) is \((n-3)^*\)-extendable iff (i) \(G\) is \(K_{2n}\), or (ii) \(\delta(G)= 2n-2\), or (iii) \(\delta(G)= 2n-3\) and the independence number of \(G\) is less than 3 (Theorem 4.3). (3) If \(G\) is a graph on \(2n\geq 10\) vertices, then \(G\) is \((n-3)^*\)-extendable iff \(G\) is \((n-2)\)-extendable and non-bipartite (Theorem 4.4).