Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657343 | Journal of Combinatorial Theory, Series B | 2008 | 11 Pages |
Abstract
A graph G with at least 2n+2 vertices is said to be n-extendable if every matching of size n in G extends to a perfect matching. It is shown that (1) if a graph is embedded on a surface of Euler characteristic χ, and the number of vertices in G is large enough, the graph is not 4-extendable; (2) given g>0, there are infinitely many graphs of orientable genus g which are 3-extendable, and given , there are infinitely many graphs of non-orientable genus which are 3-extendable; and (3) if G is a 5-connected triangulation with an even number of vertices which has genus g>0 and sufficiently large representativity, then it is 2-extendable.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics