M-alternating paths in n-extendable bipartite graphs
by
R.E.L. Aldred
Mathemaics & Statistics, University of Otago
Coauthors: D.A. Holton (University of Otago), Dingjun Lou (Zhongshan University), Akira Saito (Nihon University)

Let G be a bipartite graph with bipartition (X, Y). We say that G is n-extendable if |V(G)| = |X|+|Y| >= 2n+2, G admits a perfect matching and for each independent set of edges N subset E(G) with |N|=n, there is a perfect matching F of G such that N subset F. We are able to characterize those bipartite graphs which are n-extendable in terms of M-alternating paths between arbitrary vertices x in X and y in Y, where M is any perfect matching for G. We will present this characterization along with some generalizations.

Date received: November 8, 2000