Induced matchings in bipartite graphs (Q921017)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Induced matchings in bipartite graphs |
scientific article |
Statements
Induced matchings in bipartite graphs (English)
0 references
1989
0 references
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).
0 references
matching
0 references
bipartite graph
0 references
extremal graphs
0 references
extremal problem
0 references