×

Induced matchings in bipartite graphs. (English) Zbl 0709.05026

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).
Reviewer: S.Stahl

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
Full Text: DOI

References:

[1] Bermond, J. C.; Bond, J.; Paoli, M.; Peyrat, C., Surveys in combinatorics: Graphs and interconnection networks: Diameter and vulnerability, (Proceedings of Ninth British Combinatorial Conference, 82 (1983), London Mathematical Society), 1-30, Lecture Note Series · Zbl 0525.05018
[2] F.R.K. Chung, A. Gyárfás, W.T. Trotter and Zs. Tuza, The maximum number of edges in \(2K_2\); F.R.K. Chung, A. Gyárfás, W.T. Trotter and Zs. Tuza, The maximum number of edges in \(2K_2\)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.