کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871546 1440187 2018 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Some bounds on the zero forcing number of a graph
ترجمه فارسی عنوان
بعضی از مقادیر صفر مجبور کردن تعداد یک گراف
کلمات کلیدی
صفر اجباری،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Refining results of Amos, Caro, Davila, and Pepper, we show that Z(G)≤Δ−2Δ−1n for a connected graph G of order n and maximum degree Δ at least 3 if and only if G does not belong to {KΔ+1,KΔ,Δ,KΔ−1,Δ,G1,G2}, where G1 and G2 are two specific graphs of orders 5 and 7, respectively. For a connected graph G of order n, maximum degree 3, and girth at least 5, we show Z(G)≤n2−Ωnlogn. Using a probabilistic argument, we show Z(G)≤1−Hrr+oHrrn for an r-regular graph G of order n and girth at least 5, where Hr is the rth harmonic number. Finally, we show that Z(G)≥(g−2)(δ−2)+2 for a graph G of girth g∈{5,6} and minimum degree δ, which partially confirms a conjecture of Davila and Kenter.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 203-213
نویسندگان
, ,