Abstract: In this paper it is shown that for bipartite graphs the structure of the family of maximum independent sets can be described constructively, in the following sense. For a bipartite graph there are some “basic” maximum independent sets, in terms of which any maximum independent set can be described, in the sense that there is one-to-one correspondence between a maximum independent set and an irreducible combination of these “basic” maximum independent sets. König’s theorem states that there is duality between the cardinalities of maximum matching and minimum vertex cover. Viewing the mentioned structure, in this paper it is shown that another duality holds, which is between the sets rather than their cardinalities. We believe that this duality is not just of theoretical interest, but it also can yield to a usable algorithm for finding a maximum matching of bipartite graph. In this paper we do not present such algorithm; instead we mention what approaches we plan to use in further works to obtain such algorithm.

Keywords: bipartite graph, maximum independent set, distributive lattice, duality.

ACM Classification Keywords:G.2.1 Discrete mathematics: Combinatorics

Link:

ON THE STRUCTURE OF MAXIMUM INDEPENDENT SETS IN BIPARTITE GRAPHS

Vahagn Minasyan

http://www.foibg.com/ijita/vol17/ijita17-2-p06.pdf