The Optimal Rubbling Number of Paths, Cycles, and Grids. (5th July 2021)

• Record Type: Journal Article
• Authors: Xia, Zheng-Jiang; Hong, Zhen-Mu
• Other Names: Uddin M. Irfan Academic Editor.
• Is Part Of: Complexity. Volume 2021(2021)
• Publication Date: 2021-07-05
• Subjects: Chaotic behavior in systems -- Periodicals; Complexity (Philosophy) -- Periodicals; 003
• DOI: 10.1155/2021/5545080
• Languages: English
• ISSNs: 1076-2787

Abstract

Abstract : A pebbling move on a graph G consists of the removal of two pebbles from one vertex and the placement of one pebble on an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed, which is also called the strict rubbling move. In this new move, one pebble each is removed from u and v adjacent to a vertex w, and one pebble is added on w . The rubbling number of a graph G is the smallest number m, such that one pebble can be moved to each vertex from every distribution with m pebbles. The optimal rubbling number of a graph G is the smallest number m, such that one pebble can be moved to each vertex from some distribution with m pebbles. In this paper, we give short proofs to determine the rubbling number of cycles and the optimal rubbling number of paths, cycles, and the grid P 2 × P n ; moreover, we give an upper bound of the optimal rubbling number of P m × P n .