A subset M E(G) of the edge set E(G) of a graph G is called a matching provided that no two edges in M have a vertex in common. A perfect matching M is a matching with the property that each vertex of G is incident with an edge in M. For k a positive integer, a graph G is k-extendable provided that G has a matching of size k and every matching in G of size at most k can be extended to a perfect matching in G. | Perfect Matching Preservers Richard A. Brualdi Department of Mathematics University of Wisconsin - Madison Madison WI 53706 USA brualdi@ Martin Loebl Department of Applied Mathematics Institute for Theoretical Computer Science Charles University Malostranske namesti 25 118 00 Prague Czech Republic loebl@ Ondrej Pangrac Department of Applied Mathematics Institute for Theoretical Computer Science Charles University Malostranske namesti 25 118 00 Prague Czech Republic pangrac@ Submitted Nov 15 2004 Accepted Oct 19 2006 Published Oct 31 2006 AMS Subject Classification 05C20 05C50 05C70 Abstract For two bipartite graphs G and G a bijection p E G E G0 is called a perfect matching preserver provided that M is a perfect matching in G if and only if p M is a perfect matching in G . We characterize bipartite graphs G and G0 which are related by a matching preserver and the matching preservers between them. Supported by Ministry of Education of Czech Republic as project LN00A056. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R95 1 1 Introduction A subset M c E G of the edge set E G of a graph G is called a matching provided that no two edges in M have a vertex in common. A perfect matching M is a matching with the property that each vertex of G is incident with an edge in M. For k a positive integer a graph G is k-extendable provided that G has a matching of size k and every matching in G of size at most k can be extended to a perfect matching in G. In this paper we characterize the bipartite graphs G and G0 that are related by a matching preserver and so with appropriate labeling of edges have the same perfect matchings. We will achieve this by a full description of matching preservers defined as follows A bijection f E G E G0 is matching preserving or is a matching preserver provided that M is a perfect matching in G if and only if f M is a perfect matching in G0. Matching preservers for bipartite graphs G were investigated in 2
