Graph pebbling es un juego matemático que se juega en un gráfico con cero o más guijarros en cada uno de sus vértices . 'Game play' se compone de una serie de movimientos de guijarros. Un movimiento de guijarros en un gráfico consiste en elegir un vértice con al menos dos guijarros, quitar dos guijarros de él y agregar uno a un vértice adyacente (el segundo guijarro eliminado se descarta del juego). π ( G ), el número de guijarros de un gráfico G , es el número natural más bajo n que satisface la siguiente condición:
Dado cualquier vértice objetivo o 'raíz' en el gráfico y cualquier configuración inicial de n guijarros en el gráfico, es posible, después de una serie de movimientos de guijarros, alcanzar una nueva configuración en la que el vértice de la raíz designado tenga uno o más guijarros.
Por ejemplo, en un gráfico con 2 vértices y 1 borde que los conecta, el número de guijarros es 2. No importa cómo se coloquen los dos guijarros en los vértices del gráfico, siempre es posible mover un guijarro a cualquier vértice del gráfico. Una de las cuestiones centrales del guijarro de gráficos es el valor de π ( G ) para un gráfico G dado .
Otros temas en guijarros incluyen guijarros de cobertura, guijarros óptimos, guijarros de cobertura de dominación, límites y umbrales para números de guijarros, gráficos profundos y otros.
El juego de guijarros fue sugerido por primera vez por Lagarias y Saks, como una herramienta para resolver un problema particular en la teoría de números . En 1989 FRK Chung introdujo el concepto en la literatura [1] y definió el número de guijarros, π ( G ).
El número de guijarros para un gráfico completo en n vértices se verifica fácilmente como n : si tuviéramos ( n - 1) guijarros para poner en el gráfico, entonces podríamos poner un guijarro en cada vértice excepto en el objetivo. Como ningún vértice tiene dos o más guijarros, no es posible realizar movimientos, por lo que es imposible colocar un guijarro en el objetivo. Por lo tanto, el número de guijarros debe ser mayor que n - 1. Dados n guijarros, hay dos casos posibles. Si cada vértice tiene un guijarro, no se requieren movimientos. Si algún vértice está desnudo, al menos otro vértice debe tener dos guijarros, y un movimiento de guijarros permite agregar un guijarro a cualquier vértice de destino en el gráfico completo. [1]