关于正则二部图的Pebbling数
On the Pebbling Number of Regular Bipartite Graph
-
摘要: 图G的pebbling数f(G)是最小的正整数n, 使得不管n个pebble如何放置在G的顶点上, 总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上, 其中图G的一个pebbling移动是从一个顶点移走2个pebble, 而把其中的一个移到与其相邻的一个顶点上. 证明了具有2m个顶点的k-正则二部图的Pebbling数为2m, 其中k≥(m+1)/2.Abstract: The pebbling number f(G) of a graph G is the smallest number of positive integer n. However pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let H(m, m) be a regular bipartite graph with the vertex bipartite partition X and Y such that|X|=|Y|. In this paper, we prove that if k≥(m+1)/2, the conclusion mentioned above is right.