Pegging Numbers For Various Tree Graphs

Details Pegging Numbers For Various Tree Graphs Pegging Numbers For Various Tree Graphs

2011-03-02

arxiv.org/abs/1103.0516v1

Mathematics

Combinatorics

Scientific paper

In the game of pegging, each vertex of a graph is considered a hole into which a peg can be placed. A pegging move is performed by jumping one peg over another peg, and then removing the peg that has been jumped over from the graph. We define the pegging number as the smallest number of pegs needed to reach all the vertices in a graph no matter what the distribution. Similarly, the optimal-pegging number of a graph is defined as the smallest distribution of pegs for which all the vertices in the graph can be reached. We obtain tight bounds on the pegging numbers and optimal-pegging numbers of complete binary trees and compute the optimal-pegging numbers of complete infinitary trees. As a result of these computations, we deduce that there is a tree whose optimal-pegging number is strictly increased by removing a leaf. We also compute the optimal-pegging number of caterpillar graphs and the tightest upper bound on the optimal-pegging numbers of lobster graphs.

Affiliated with

Also associated with

No associations

Rating

Pegging Numbers For Various Tree Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pegging Numbers For Various Tree Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pegging Numbers For Various Tree Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-475360