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

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
نویسندگان
, ,