We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Cycles and Girth in Pebble Assignment Graphs.
- Authors
Fiorini, E.; Johnston, G.; Lind, M.; Woldar, A.; Wong, T. W. H.
- Abstract
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 2ncan 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 , ∞ when G is a forest.
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 5, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-022-02552-5