Lollipop and Cubic Weight Functions for Graph Pebbling
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912131290497024 |
|---|---|
| author | Yang, Marshall Yerger, Carl Zhou, Runtian |
| author_facet | Yang, Marshall Yerger, Carl Zhou, Runtian |
| contents | Given a configuration of pebbles on the vertices of a graph $G$, a pebbling move removes two pebbles from a vertex and puts one pebble on an adjacent vertex. The pebbling number of a graph $G$ is the smallest number of pebbles required such that, given an arbitrary initial configuration of pebbles, one pebble can be moved to any vertex of $G$ through some sequence of pebbling moves. Through constructing a non-tree weight function for $Q_4$, we improve the weight function technique, introduced by Hurlbert and extended by Cranston et al., that gives an upper bound for the pebbling number of graphs. Then, we propose a conjecture on weight functions for the $n$-dimensional cube. We also construct a set of valid weight functions for variations of lollipop graphs, extending previously known constructions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_00580 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Lollipop and Cubic Weight Functions for Graph Pebbling Yang, Marshall Yerger, Carl Zhou, Runtian Combinatorics Given a configuration of pebbles on the vertices of a graph $G$, a pebbling move removes two pebbles from a vertex and puts one pebble on an adjacent vertex. The pebbling number of a graph $G$ is the smallest number of pebbles required such that, given an arbitrary initial configuration of pebbles, one pebble can be moved to any vertex of $G$ through some sequence of pebbling moves. Through constructing a non-tree weight function for $Q_4$, we improve the weight function technique, introduced by Hurlbert and extended by Cranston et al., that gives an upper bound for the pebbling number of graphs. Then, we propose a conjecture on weight functions for the $n$-dimensional cube. We also construct a set of valid weight functions for variations of lollipop graphs, extending previously known constructions. |
| title | Lollipop and Cubic Weight Functions for Graph Pebbling |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2310.00580 |