Premium
Perfect Matchings of Regular Bipartite Graphs
Author(s) -
Lukot'ka Robert,
Rollová Edita
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22076
Subject(s) - combinatorics , mathematics , bipartite graph , complete bipartite graph , edge transitive graph , line graph , discrete mathematics , foster graph , strong perfect graph theorem , graph , perfect graph theorem , factor critical graph , cubic graph , complement graph , voltage graph , 1 planar graph
Let G be a regular bipartite graph and X ⊆ E ( G ) . 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 ( G , X ) , that is a graph G with exactly the edges from X being negative, is not equivalent to ( G , ∅ ) . 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.