کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8902939 1632396 2018 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Independence-domination duality in weighted graphs
ترجمه فارسی عنوان
دوگانگی مستقل بودن سلطه در نمودارهای وزن
کلمات کلیدی
نمودار وزن، استقلال مشترک، سلطه جمعی، تسلط، متقاطع
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Given a partition V=(V1,…,Vm) of the vertex set of a graph G, an independent transversal (IT) is an independent set in G that contains one vertex from each Vi. A fractional IT is a non-negative real valued function on V(G) that represents each part with total weight at least 1, and belongs as a vector to the convex hull of the incidence vectors of independent sets in the graph. It is known that if the domination number of the graph induced on the union of every k parts Vi is at least k, then there is a fractional IT. We prove a weighted version of this result. This is a special case of a general conjecture, on the weighted version of a duality phenomenon, between independence and domination in pairs of graphs on the same vertex set.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 8, August 2018, Pages 2332-2336
نویسندگان
, ,