کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8902917 1632396 2018 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The list L(2,1)-labeling of planar graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The list L(2,1)-labeling of planar graphs
چکیده انگلیسی
Let N be the set of all positive integers. A list assignment of a graph G is a function L:V(G)⟶2N that assigns each vertex v a list L(v) for all v∈V(G). We say that G is L-(2,1)-choosable if there exists a function ϕ such that ϕ(v)∈L(v) for all v∈V(G), |ϕ(u)−ϕ(v)|≥2 if u and v are adjacent, and |ϕ(u)−ϕ(v)|≥1 if u and v are at distance 2. The list-L(2,1)-labeling number λl(G) of G is the minimum k such that for every list assignment L={L(v):|L(v)|=k,v∈V(G)}, G is L-(2,1)-choosable. We prove that if G is a planar graph with girth g≥8 and its maximum degree Δ is large enough, then λl(G)≤Δ+3. There are graphs with large enough Δ and g≥8 having λl(G)=Δ+3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 8, August 2018, Pages 2211-2219
نویسندگان
, , , , ,