Cycles and Girth in Pebble Assignment Graphs

被引：0

作者：

Fiorini, E. ^{[1
]}

Johnston, G. ^{[2
]}

Lind, M. ^{[3
]}

Woldar, A. ^{[2
]}

Wong, T. W. H. ^{[4
]}

机构：

[1] Rutgers State Univ, Dimacs, Piscataway, NJ 08854 USA

[2] Villanova Univ, Villanova, PA 19085 USA

[3] Univ Scholars Program, W Chester, PA 19380 USA

[4] Kutztown Univ Penn, Kutztown, PA 19530 USA

来源：

GRAPHS AND COMBINATORICS | 2022年 / 38卷 / 05期

关键词：

Pebbling; cycles; Girth; Assignment graph; Multiassignment graph; Endstates; Dominance;

D O I：

10.1007/s00373-022-02552-5

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页数：20