Name
Abstract | ||
|---|---|---|
Consider a connected graph and a configuration of pebbles on its vertices. A pebbling step consists of removing two pebbles from a vertex and placing one on an adjacent vertex. A configuration is called solvable if it is possible to place a pebble on any given vertex through a sequence of pebbling steps. A smallest number $t$ such that any configuration with $t$ pebbles is solvable is called the pebbling number of the graph. In this paper, we consider algorithms determining the solvability of a pebbling configuration on graphs of diameter two. We prove that if $k$ is the vertex connectivity of a diameter two graph $G$, then a configuration is solvable if there are at least $c(k)=\min\{k+4,3k-1\}$ vertices in $G$ with two or more pebbles. We use this result to construct an algorithm that has complexity $O(c(k)!\cdot n^{2c(k)-3}m)$, where $n$ is the number of vertices and $m$ is the number of edges. We also present an algorithm for diameter two graphs with pebbling number $n+1$, known as Class 1 graphs, which takes $O(nm)$ time. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/080724277 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
pebbling number,vertex connectivity,adjacent vertex,pebbling configuration,connected graph,pebbling step,cdot n,smallest number,pebbling algorithms,diameter,connectivity,algorithms | Graph algorithms,Discrete mathematics,Graph,Combinatorics,Two-graph,Vertex (geometry),Algorithm complexity,Neighbourhood (graph theory),Algorithm,Vertex connectivity,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
23 | 2 | 0895-4801 |
Citations | PageRank | References |
6 | 0.70 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Airat Bekmetjev | 1 | 24 | 3.71 |
| Charles A. Cusack | 2 | 22 | 4.89 |