Graph pegging numbers

DOI10.1016/J.DISC.2008.03.029MaRDI QIDQ1025451zbMATH OpenOpenAlexFDO

Authors Madeeha Khalid, David Petrie Moulton, Philip Matchett Wood, Geir T. Helleloid

Publication date 19 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

pebbling numbergraph pebblinggraph peggingpegging number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Abstract: In graph pegging, we view each vertex of a graph as a hole into which a peg can be placed, with checker-like ``pegging moves allowed. Motivated by well-studied questions in graph pebbling, we introduce two pegging quantities. The pegging number (respectively, the optimal pegging number) of a graph is the minimum number of pegs such that for every (respectively, some) distribution of that many pegs on the graph, any vertex can be reached by a sequence of pegging moves. We prove several basic properties of pegging and analyze the pegging number and optimal pegging number of several classes of graphs, including paths, cycles, products with complete graphs, hypercubes, and graphs of small diameter.

Recommendations

• Pegging numbers for various tree graphs.
• scientific article; zbMATH DE number 1040545
• The Pivot number of a graph
• Pebbling numbers of some graphs
• Graph reconstruction numbers
• Ranking numbers of graphs
• scientific article; zbMATH DE number 4110746
• scientific article; zbMATH DE number 1071742

Cites work

• scientific article; zbMATH DE number 1439473 (Why is no real title available?)
• A nonconstructive upper bound on covering radius
• Diagonal checker-jumping and Eulerian numbers for color-signed permutations
• On Moore Graphs with Diameters 2 and 3
• Optimally pebbling hypercubes and powers
• Pebbling in Hypercubes
• Pebbling in diameter two graphs and products of paths
• Pegging numbers for various tree graphs.
• Solitaire army and related games

Cited in

(7)

• Cup stacking in graphs
• Graphs that admit a Hamilton path are cup-stackable
• Pagoda functions for peg solitaire on graphs
• Threshold and complexity results for the cover pebbling game
• Lower against number in graphs
• Peg solitaire on graphs -- a survey
• Pegging numbers for various tree graphs.

This page was built for publication: Graph pegging numbers

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