کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949620 | 1440197 | 2017 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Further results on the deficiency of graphs
ترجمه فارسی عنوان
نتایج بیشتر در مورد کمبود نمودارها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
لبه رنگ مناسب، فاصله (متوالی) رنگ آمیزی، کمبود، گراف کامل گراف کامل نزدیک
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 226, 31 July 2017, Pages 117-126
نویسندگان
P.A. Petrosyan, H.H. Khachatrian,