Cycles and Girth in Pebble Assignment Graphs

An assignment graph [SG]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[S_G]$$\end{document} is a single-rooted Hasse diagram depicting all possible states resulting from a prescribed pebble assignment SG\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S_G$$\end{document} on a simple graph G. In this paper, we construct assignment graphs of every possible (even) girth and give necessary and sufficient conditions for [SG]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[S_G]$$\end{document} 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 [SG]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[S_G]$$\end{document} is limited to 4,6,∞\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$4,6,\infty $$\end{document} when G is a forest.