کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776770 | 1413640 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Lemke graphs and Graham's pebbling conjecture
ترجمه فارسی عنوان
نمودارهای لمک و حدس غم انگیز گراهام
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number
Ï(G) is the smallest positive integer such that for every distribution of Ï(G) pebbles and every vertex v, a pebble can be moved to v. Graham conjectured that Ï(Gâ¡H)â¤Ï(G)Ï(H) for any connected graphs G and H, where Gâ¡H denotes the Cartesian product of G and H. A graph G has the 2-pebbling property (respectively, the odd-2-pebbling property) if for any distribution with more than 2Ï(G)âq (respectively, 2Ï(G)âr) pebbles, where q is the number of vertices with at least one pebble (respectively, r is the number of vertices with an odd number of pebbles), it is possible, using pebbling moves, to get two pebbles to any vertex. Obviously, graphs which have the 2-pebbling property also have the odd-2-pebbling property. A graph G without the 2-pebbling property is called a Lemke graph. In this paper, we further extend the concept of the odd-2-pebbling property to the weak odd-2-pebbling property and show that all Lemke graphs found to date have the weak odd-2-pebbling property, but not the odd-2-pebbling property. Moreover, we also prove that Ï(Lâ¡T)â¤Ï(L)Ï(T) and Ï(Lâ¡Kn)â¤Ï(L)Ï(Kn), where T is a tree, Kn is the complete graph on n vertices and L is a known Lemke graph. The two evidences supporting Graham's conjecture differ from the previous evidences requiring that G and H have the 2-pebbling property.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 9, September 2017, Pages 2318-2332
Journal: Discrete Mathematics - Volume 340, Issue 9, September 2017, Pages 2318-2332
نویسندگان
Ze-Tu Gao, Jian-Hua Yin,