TAILIEUCHUNG - Báo cáo toán học: "The t-pebbling number is eventually linear in t "

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: The t-pebbling number is eventually linear in t. | The t-pebbling number is eventually linear in t Michael Hoffmann ETH Zurich Switzerland hoffmann@ Jiri Matousek Charles University Prague Czech Republic matousek@ Yoshio Okamoto JAIST Nomi Japan okamotoy@j Philipp Zumstein ETH Zuurich Switzerland zuphilip@ Submitted Apr 4 2010 Accepted Jun 22 2011 Published Jul 22 2011 Mathematics Subject Classification 05C99 05C35 Abstract In graph pebbling games one considers a distribution of pebbles on the vertices of a graph and a pebbling move consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The t-pebbling number nt G of a graph G is the smallest m such that for every initial distribution of m pebbles on V G and every target vertex x there exists a sequence of pebbling moves leading to a distibution with at least t pebbles at x. Answering a question of Sieben we show that for every graph G nt G is eventually linear in t that is there are numbers a b t0 such that nt G at b for all t to. Our result is also valid for weighted graphs where every edge e u v has some integer weight w e 2 and a pebbling move from u to v removes w e pebbles at u and adds one pebble to v. 1 Introduction Let G V E be an undirected graph. A pebbling distribution on G is a function p V No 0 1 2 . . A pebbling move consists of taking two pebbles off a vertex u and adding one pebble on an adjacent vertex v we can think of this as paying a toll of one pebble for using the edge u v . We also say that we move one pebble from u to v. More generally we consider a graph G together with a weight function u E 2 3 4 . on edges. If an edge e u v has weight u e then we pay a toll of Supported by Global COE Program Computationism as a Foundation for the Sciences and Grantin-Aid for Scientific Research from Ministry of Education Science and Culture Japan and Japan Society for the Promotion of Science. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P153 1 w e 1 pebbles for moving one .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học