Pebbling number of polymers

Abstract

Let $G=(V,E)$ be a simple graph. A function $f:V\to \mathbb{N}\cup \{0\}$ is called a configuration of pebbles on the vertices of $G$ and the quantity $|f|={\sum }_{u\in V}f(u)$ is called the weight of $f$ which is just the total number of pebbles assigned to vertices. A pebbling step from a vertex $u$ to one of its neighbors $v$ reduces $f(u)$ by two and increases $f(v)$ by one. A pebbling configuration $f$ is said to be solvable if for every vertex $v$, there exists a sequence (possibly empty) of pebbling moves that results in a pebble on $v$. The pebbling number $\pi (G)$ equals the minimum number $k$ such that every pebbling configuration $f$ with $|f|=k$ is solvable. Let $G$ be a connected graph constructed from pairwise disjoint connected graphs $G_1,...,G_k$ by selecting a vertex of $G_1$, a vertex of $G_2$, and identifying these two vertices. Then continue in this manner inductively. We say that $G$ is a polymer graph, obtained by point-attaching from monomer units $G_1,...,G_k$. In this paper, we study the pebbling number of some polymers.

15 pages, 9 figures