Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 8 of 8 for “"pebbling"”.
-
On the Pebbling Numbers of Graphs
Graph pebbling is an application which has evolved from the study of graph theory. The goal of pebbling in a graph is to use pebbling steps to move one pebble onto a designated root vertex. A pebbling step is produced by taking two pebbles from a vertex, moving one of them to an adjacent vertex, …
-
Clause Learning, Resolution Space, and Pebbling
… regarding the relationship between Black-White Pebbling and Resolution. In fact, determining the complexity of Resolution variable space required us to first prove that Black-White Pebbling is PSPACE-complete. The complexity of the Black-White Pebbling Game has remained an open problem for 30 …
-
Pebbling in Erdős-Rényi random graphs
Graph pebbling is a game in which a collection of pebbles is placed on the vertices of a connected graph. A pebbling move consists of removing two pebbles from one vertex and placing a pebble on any adjacent vertex. Of interest is the pebbling number of a graph G: the least k such that for any …
-
Covering cover pebbling number of products of paths
There are a variety of pebbling numbers, such as classical pebbling number, cover pebbling number, and covering cover pebbling number. In this paper we determine the covering cover pebbling number for Cartesian products of paths. The covering cover pebbling number of a graph, G, is the smallest …
-
On t-Restricted Optimal Rubbling of Graphs
… where each vertex begins with f(v) pebbles. A pebbling move takes two pebbles from some vertex adjacent to v and places one pebble on v. A rubbling move takes one pebble from each of two vertices that are adjacent to v and places one pebble on v. A vertex x is reachable under a pebbling …
-
Roman Domination Cover Rubbling
… which is Roman dominating after some sequence of pebbling and rubbling moves. We begin by characterizing graphs $G$ having small $\rho_{R}(G)$ value. Among other things, we also obtain the Roman domination cover rubbling number for paths and give an upper bound for the Roman domination cover …
-
Composing classical and quantum relaxations of CSP and structure isomorphism
… game comonads like the Ehrenfeucht-Fraïssé and pebbling comonads do not distribute over many important distribution minion monads, such as the basic linear programming and arc-consistency monads. On the positive side, we identify sufficient conditions under which a distributive law between game …
-
Arboreal covers over relational structures
… program was on the relationship between the pebbling comonad and the distribution-like quantum monad, defined by Abramsky, Barabosa, de Silva and Zapata in 2017, used to capture the notion of quantum homomorphism. By tailoring the definition of the Ehrenfeucht-{\Fraisse} comonad and quantum …