Cycles and Girth in Pebble Assignment Graphs

An assignment graph [S-G] is a single-rooted Hasse diagram depicting all possible states resulting from a prescribed pebble assignment S-G on a simple graph G. In this paper, we construct assignment graphs of every possible (even) girth and give necessary and sufficient conditions for [S-G] to have girth 4. We extend the notion of an assignment graph to that of a multiassignment graph (a multirooted Hasse diagram formed by amalgamating two or more assignment graphs on G) and resolve the question: When can a multiassignment graph be a subgraph of some assignment graph? Resolution of this question is critical to our main result: Every possible cycle type of girth at most 2n can be simultaneously realized in a suitable assignment graph. The paper concludes with a proof that the girth of [S-G] is limited to 4,6, infinity when G is a forest.