Spelling suggestions: "subject:"cover bubbling"" "subject:"cover babbling""
1 |
Threshold and Complexity Results for the Cover Pebbling GameGodbole, Anant P., Watson, Nathaniel G., Yerger, Carl R. 06 June 2009 (has links)
Given a configuration of pebbles on the vertices of a graph, a pebbling move is defined by removing two pebbles from some vertex and placing one pebble on an adjacent vertex. The cover pebbling number of a graph, γ (G), is the smallest number of pebbles such that through a sequence of pebbling moves, a pebble can eventually be placed on every vertex simultaneously, no matter how the pebbles are initially distributed. We determine Bose-Einstein and Maxwell-Boltzmann cover pebbling thresholds for the complete graph. Also, we show that the cover pebbling decision problem is NP-complete.
|
2 |
Cover Pebbling Thresholds for the Complete GraphGodbole, Anant P., Watson, Nathaniel G., Yerger, Carl R. 15 October 2005 (has links)
We obtain first-order cover pebbling thresholds of the complete graph for Maxwell Boltzmann and Bose Einstein configurations.
|
3 |
Domination Cover RubblingBeeler, Robert A., Haynes, Teresa W., Keaton, Rodney 15 May 2019 (has links)
Let G be a connected simple graph with vertex set V and a distribution of pebbles on V. The domination cover rubbling number of G is the minimum number of pebbles, so that no matter how they are distributed, it is possible that after a sequence of pebbling and rubbling moves, the set of vertices with pebbles is a dominating set of G. We begin by characterizing the graphs having small domination cover rubbling numbers and determining the domination cover rubbling number of several common graph families. We then give a bound for the domination cover rubbling number of trees and characterize the extremal trees. Finally, we give bounds for the domination cover rubbling number of graphs in terms of their domination number and characterize a family of the graphs attaining this bound.
|
Page generated in 0.0762 seconds