关于正则二部图的Pebbling数  

On the Pebbling Number of Regular Bipartite Graph

作　　者：高泽图[1] 

机构地区：[1]海南大学信息科学技术学院,海南海口570228

出　　处：《海南大学学报（自然科学版）》2008年第3期225-230,共6页Natural Science Journal of Hainan University

基　　金：海南省自然科学基金项目(807026)

摘　　要：图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上,其中图G的一个pebbling移动是从一个顶点移走2个pebble,而把其中的一个移到与其相邻的一个顶点上.证明了具有2m个顶点的k-正则二部图的Pebbling数为2m,其中k≥「(m+1)/2﹁.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.

关 键 词：PEBBLING 正则二部图 传送子图 

分 类 号：O157.5[理学—数学]