کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657343 1343732 2008 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the matching extendability of graphs in surfaces
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the matching extendability of graphs in surfaces
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 98, Issue 1, January 2008, Pages 105-115