کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651126 | 1342521 | 2006 | 9 صفحه PDF | دانلود رایگان |
A graph G is said to be bicritical if G-u-vG-u-v has a perfect matching for every choice of a pair of points uu and vv. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+22k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k -extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn)O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.
Journal: Discrete Mathematics - Volume 306, Issue 13, 6 July 2006, Pages 1415–1423