A Novel Characterization of \(n\)-Extendable Bipartite Graphs

Abstract

Let \(G\) be a simple connected graph. For a subset \(S\) of \(V(G)\) with \(|S| = 2n + 1\), let \(\alpha_{(2n+1)}(G,S)\) denote the graph obtained from \(G\) by contracting \(S\) to a single vertex. The graph \(\alpha_{(2n+1)}(G, S)\) is also said to be obtained from \(G\) by an \(\alpha_{(2n+1)}\)-contraction. For pairwise disjoint subsets \(S_1, S_2, \ldots, S_{2n}\) of \(V(G)\), let \(\beta_n(G, S_1, S_2, \ldots, S_{2n})\) denote the graph obtained from \(G\) by contracting each \(S_i\) (\(i = 1, 2, \ldots, 2n\)) to a single vertex respectively. The graph \(\beta_{2n}(G, S_1, S_2, \ldots, S_{2n})\) is also said to be obtained from \(G\) by a \(\beta_{2n}\)-contraction. In the present paper, based on \(\alpha_{(2n+1)}\)-contraction and \(\beta_{2}\)-contraction, some new characterizations for \(n\)-extendable bipartite graphs are given.