Source author record

Christopher Stocker

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Reversible peg solitaire on graphs

The game of peg solitaire on graphs was introduced by Beeler and Hoilman in 2011. In this game, pegs are initially placed on all but one vertex of a graph $G$ . If $xyz$ forms a path in $G$ and there are pegs on vertices $x$ and $y$ but not $z$ , then a {\em jump} places a peg on $z$ and removes the pegs from $x$ and $y$ . A graph is called solvable if, for some configuration of pegs occupying all but one vertex, some sequence of jumps leaves a single peg. We study the game of {\em reversible peg solitaire}, where there are again initially pegs on all but one vertex, but now both jumps and unjumps (the reversal of a jump) are allowed. We show that in this game all non-star graphs that contain a vertex of degree at least three are solvable, that cycles and paths on $n$ vertices, where $n$ is divisible by $2$ or $3$ , are solvable, and that all other graphs are not solvable. We also classify the possible starting hole and ending peg positions for solvable graphs.

preprint2010arXiv

Overlap Number of Graphs

An {\it overlap representation} of a graph $G$ assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The {\it overlap number} $\ol(G)$ (introduced by Rosgen) is the minimum size of the union of the sets in such a representation. We prove the following: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2. (2) If $δ(G)\ge 2$ and $G\ne K_3$ , then $\ol(G)\le |E(G)|-1$, with equality when $G$ is connected and triangle-free and has no star-cutset. (3) If $G$ is an $n$ -vertex plane graph with $n\ge5$ , then $\ol(G)\le 2n-5$, with equality when every face has length 4 and there is no star-cutset. (4) If $G$ is an $n$ -vertex graph with $n\ge 14$ , then $\ol(G)\le \floor{n^2/4-n/2-1}$, and this is sharp (for even $n$ , equality holds when $G$ arises from $K_{n/2,n/2}$ by deleting a perfect matching).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.