کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657522 1343745 2006 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A pair of forbidden subgraphs and perfect matchings
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A pair of forbidden subgraphs and perfect matchings
چکیده انگلیسی

In this paper, we study the relationship between forbidden subgraphs and the existence of a matching. Let H be a set of connected graphs, each of which has three or more vertices. A graph G is said to be H-free if no graph in H is an induced subgraph of G. We completely characterize the set H such that every connected H-free graph of sufficiently large even order has a perfect matching in the following cases.(1)Every graph in H is triangle-free.(2)H consists of two graphs (i.e. a pair of forbidden subgraphs).A matching M in a graph of odd order is said to be a near-perfect matching if every vertex of G but one is incident with an edge of M. We also characterize H such that every H-free graph of sufficiently large odd order has a near-perfect matching in the above cases.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 96, Issue 3, May 2006, Pages 315-324