کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646879 1342316 2016 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The difference and ratio of the fractional matching number and the matching number of graphs
ترجمه فارسی عنوان
تفاوت و نسبت عدد تطبیق کسری و عدد تطبیق نمودارها
کلمات کلیدی
عدد تطبیق؛ عدد تطبیق کسری
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Given a graph GG, the matching number   of GG, written α′(G)α′(G), is the maximum size of a matching in GG, and the fractional matching number   of GG, written αf′(G), is the maximum size of a fractional matching of GG. In this paper, we prove that if GG is an nn-vertex connected graph that is neither K1K1 nor K3K3, then αf′(G)−α′(G)≤n−26 and αf′(G)α′(G)≤3n2n+2. Both inequalities are sharp, and we characterize the infinite family of graphs where equalities hold.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 4, 6 April 2016, Pages 1382–1386
نویسندگان
, , ,