کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949620 1440197 2017 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Further results on the deficiency of graphs
ترجمه فارسی عنوان
نتایج بیشتر در مورد کمبود نمودارها
کلمات کلیدی
لبه رنگ مناسب، فاصله (متوالی) رنگ آمیزی، کمبود، گراف کامل گراف کامل نزدیک
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A proper t-edge-coloring of a graph G is a mapping α:E(G)→{1,…,t} such that all colors are used, and α(e)≠α(e′) for every pair of adjacent edges e,e′∈E(G). If α is a proper edge-coloring of a graph G and v∈V(G), then the spectrum of a vertex v, denoted by S(v,α), is the set of all colors appearing on edges incident to v. The deficiency of α at vertex v∈V(G), denoted by def(v,α), is the minimum number of integers which must be added to S(v,α) to form an interval, and the deficiency def(G,α) of a proper edge-coloring α of G is defined as the sum ∑v∈V(G)def(v,α). The deficiency of a graph G, denoted by def(G), is defined as follows: def(G)=minαdef(G,α), where minimum is taken over all possible proper edge-colorings of G. For a graph G, the smallest and the largest values of t for which it has a proper t-edge-coloring α with deficiency def(G,α)=def(G) are denoted by wdef(G) and Wdef(G), respectively. In this paper, we obtain some bounds on wdef(G) and Wdef(G). In particular, we show that for any l∈N, there exists a graph G such that def(G)>0 and Wdef(G)−wdef(G)≥l. It is known that for the complete graph K2n+1, def(K2n+1)=n (n∈N). Recently, Borowiecka-Olszewska, Drgas-Burchardt and Hałuszczak posed the following conjecture on the deficiency of near-complete graphs: if n∈N, then def(K2n+1−e)=n−1. In this paper, we confirm this conjecture.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 226, 31 July 2017, Pages 117-126
نویسندگان
, ,