Two-player pebbling on diameter 2 graphs

DOI10.1007/S00182-021-00766-0MaRDI QIDQ2041086zbMATH OpenOpenAlexFDO

Authors Garth Isaak, Matthew Prudente

Publication date 15 July 2021

Published in International Journal of Game Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.08550

zbMATH Keywords

game theorygraph pebblinggraph theory

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) 2-person games (91A05) Games involving graphs (91A43)

Abstract: A pebbling move refers to the act of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. The goal of graph pebbling is: Given an initial distribution of pebbles, use pebbling moves to reach a specified goal vertex called the root. The pebbling number of a graph $pi(G)$ is the minimum number of pebbles needed so every distribution of $pi(G)$ pebbles can reach every choice of the root. We introduce a new variant of graph pebbling, a game between two players. One player aims to move a pebble to the root and the other player aims to prevent this. We show configurations of various classes of graphs for which each player has a winning strategy. We will characterize the winning player for a specific class of diameter two graphs.

Recommendations

• On Pebbling Graphs by Their Blocks
• t-pebbling the graphs of diameter two
• Pebbling graphs of diameter three and four
• Optimal pebbling of graphs
• The complexity of pebbling in diameter two graphs

Cites work

• An addition theorem on the integers modulo n
• General graph pebbling
• scientific article; zbMATH DE number 398953 (Why is no real title available?)
• scientific article; zbMATH DE number 1145909 (Why is no real title available?)
• scientific article; zbMATH DE number 2004829 (Why is no real title available?)
• scientific article; zbMATH DE number 1439473 (Why is no real title available?)
• Lessons in play. An introduction to combinatorial game theory
• Pebbling in Hypercubes
• Random-player maker-breaker games

Cited in

(8)

• On Pebbling Graphs by Their Blocks
• Pebbling Algorithms in Diameter Two Graphs
• Characterizing winning positions in the impartial two-player pebbling game on complete graphs
• Generalized impartial two-player pebbling games on K₃ and C₄
• On the secure vertex cover pebbling number
• The t-pebbling number and 2t-pebbling property of rooted product of some graphs
• A pebbling game on powers of paths
• On two-player pebbling

This page was built for publication: Two-player pebbling on diameter 2 graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2041086)