𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A comparison of two variations of a pebble game on graphs

✍ Scribed by Friedhelm Meyer auf der Heide

Publisher
Elsevier Science
Year
1981
Tongue
English
Weight
347 KB
Volume
13
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

The number of pebbles used in the black [black-white] pebble game corresponds to the storage requirement of the deterministic [non-deterministic] evaluation of a straight line program. Suppose a distinguished vertex of a directed acyclic graph can be pebbled with k pebbles in the black-white pebble game. Then it can be pebbled with k'<~k(k-1)+l pebbles in the black pebble game.

πŸ“œ SIMILAR VOLUMES

A game of cops and robbers played on pro
A game of cops and robbers played on products of graphs
✍ S. Neufeld; R. Nowakowski πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 825 KB

The game of cops and robbers is played with a set of 'cops' and a 'robber' who occupy some vertices of a graph. Both sides have perfect information and they move alternately to adjacent vertices. The robber is captured if at least one of the cops occupies the same vertex as the robber. The problem i

A game of two halves
A game of two halves
✍ Bob Palmer πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 27 KB
Degree-bounded coloring of graphs: Varia
Degree-bounded coloring of graphs: Variations on a theme by brooks
✍ S. L. Hakimi; J. Mitchem; E. F. Schmeichel πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 876 KB

## Abstract A graph __G__ is degree‐bounded‐colorable (briefly, db‐colorable) if it can be properly vertex‐colored with colors 1,2, …, k ≀ Ξ”(__G__) such that each vertex __v__ is assigned a color __c__(__v__) ≀ __v__. We first prove that if a connected graph __G__ has a block which is neither a com