کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871546 | 1440187 | 2018 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Some bounds on the zero forcing number of a graph
ترجمه فارسی عنوان
بعضی از مقادیر صفر مجبور کردن تعداد یک گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
صفر اجباری،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 203-213
نویسندگان
Michael Gentner, Dieter Rautenbach,