Induced matchings in bipartite graphs (Q921017)

All the graphs in this paper are understood to be finite, undirected, without loops or multiple edges. An induced \((k+1)\)-matching of the graph G is an induced subgraph that consists of \(k+1\) independent edges of G. The authors prove several extremal results of this concept. A bipartite graph of maximum degree d without an induced \((k+1)\)-matching can have at most \(kd^ 2\) edges (Theorem 1). The extremal graphs for \(k>1\) are not unique but can be completely described (Theorem 2). When the extremal problem for \(k>2\) is restricted to connected bipartite graphs, the extremal problem drops by at least d (Theorem 3).