Perfect Matchings of Regular Bipartite Graphs |
| |
| Authors: | Robert Lukot'ka Edita Rollová |
| |
| Affiliation: | 1. FACULTY OF MATHEMATICS, PHYSICS AND INFORMATICS, COMENIUS UNIVERSITY, MLYNSKá DOLINA, BRATISLAVA, SLOVAKIAContract grant sponsor: VEGA;2. Contract grant number: 1/0042/14.;3. NEW TECHNOLOGIES FOR THE INFORMATION SOCIETY, FACULTY OF APPLIED SCIENCES, UNIVERSITY OF WEST BOHEMIA, PLZE?, CZECH REPUBLICContract grant sponsor: Czech Science Foundation;4. Contract grant number: GA14‐19503S;5. Contract grant sponsor: Czech Ministry of Education, Youth and Sports;6. Contract grant number: LO1506;7. Contract grant sponsor: European Social Fund and the state budget of the Czech republic;8. Contract grant number: NEXLIZ CZ.1.07/2.3.00/30.0038. |
| |
| Abstract: | Let G be a regular bipartite graph and  . We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph  , that is a graph G with exactly the edges from X being negative, is not equivalent to  . In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2‐cycle‐cover such that each cycle contains an odd number of negative edges. |
| |
| Keywords: | perfect matching regular graph bipartite graph |
|
|
. We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph 
, that is a graph G with exactly the edges from X being negative, is not equivalent to 
. In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2‐cycle‐cover such that each cycle contains an odd number of negative edges.