کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872387 681740 2014 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank
ترجمه فارسی عنوان
برای تعداد تطبیق، تعداد رنگی لبه و تعداد استقلال یک گراف در رتبه، محدودیت دارد
کلمات کلیدی
رتبه گراف، تطبیق شماره، شاخص کروماتیک، تعداد استقلال،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let G=(V,E) be a simple graph with vertex set V and edge set E. The rank of G, written as r, is defined to be the rank of its adjacency matrix. Let c denote e−v+θ, where e=|E|, v=|V| and θ means the number of connected components of G, and let m,α,χ′ respectively be the matching number, the independence number, and the chromatic index of G. In this paper, it is proved that ⌈r−c2⌉≤m≤⌊r+2c2⌋, ⌈2er+2c⌉≤χ′, and v−⌊r2⌋−c≤α≤v−⌈r2⌉. Examples are given to show that all the bounds can be attained.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 166, 31 March 2014, Pages 276-281
نویسندگان
, ,