کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647555 | 1342359 | 2013 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Generalizing Tutte’s theorem and maximal non-matchable graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A graph GG has a perfect matching if and only if 00 is not a root of its matching polynomial μ(G,x)μ(G,x). Thus, Tutte’s famous theorem asserts that 00 is not a root of μ(G,x)μ(G,x) if and only if codd(G−S)≤|S| for all S⊆V(G)S⊆V(G), where codd(G) denotes the number of odd components of GG. Tutte’s theorem can be proved using a characterization of the structure of maximal non-matchable graphs, that is, the edge-maximal graphs among those having no perfect matching. In this paper, we prove a generalized version of Tutte’s theorem in terms of avoiding any given real number θθ as a root of μ(G,x)μ(G,x). We also extend maximal non-matchable graphs to maximal θθ-non-matchable graphs and determine the structure of such graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 20, 28 October 2013, Pages 2162–2167
Journal: Discrete Mathematics - Volume 313, Issue 20, 28 October 2013, Pages 2162–2167
نویسندگان
Cheng Yeaw Ku, Kok Bin Wong,