Back to Search
Start Over
Construction for bicritical graphs and k-extendable bipartite graphs
- Source :
-
Discrete Mathematics . Jul2006, Vol. 306 Issue 13, p1415-1423. 9p. - Publication Year :
- 2006
-
Abstract
- Abstract: A graph G is said to be bicritical if has a perfect matching for every choice of a pair of points and . 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 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 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. [Copyright &y& Elsevier]
- Subjects :
- *GRAPH theory
*ALGEBRA
*COMBINATORICS
*TOPOLOGY
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 306
- Issue :
- 13
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 21190115
- Full Text :
- https://doi.org/10.1016/j.disc.2005.12.025