MATHEMATICAL ENGINEERING TECHNICAL REPORTS Square-Free 2-Matchings in Bipartite Graphs and Jump Systems
Yusuke Kobayashi, Kenjiro Takazawa · 2008
For an undirected graph and a fixed integer k, a 2-matching is said to be Ck-free if it has no cycle of length k or less. In particular, a C4-free 2-matching in a bipartite graph is called a square-free 2-matching. The problem of finding a maximum Ck-free 2-matching in a bipartite graph is NP-hard when k ≥ 6, and polynomially solvable when k = 4. Also, the problem of finding a maximum-weight Ck-free 2-matching in a bipartite graph is NP-hard for any integer k ≥ 4, and polynomially solvable when k = 4 and the weight function is vertex-induced on every cycle of length four. In this paper, we prove that the degree sequences of the Ck-free 2-matchings in a bipartite graph form a jump system for k = 4, and do not always form a jump system for k ≥ 6. This result is consistent with the polynomial solvability of the Ck-free 2-matching problem in bipartite graphs and partially proves the conjecture of Cunningham that the degree sequences of C4-free 2-matchings form a jump system for any graph. We also show that the weighted square-free 2-matchings in a bipartite graph induce an M-concave (M-convex) function on the jump system if and only if the weight function is vertex-induced on every square. This result is also consistent with the polynomial solvability of the weighted square-free 2-matching problem.