Two-pebbling and odd-two-pebbling are not equivalent
| Autor: | Charles A. Cusack, Airat Bekmetjev, Mark Powers |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Theoretical Computer Science Vertex (geometry) Combinatorics Integer 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Pebble Connectivity Mathematics |
| Zdroj: | Discrete Mathematics. 342:777-783 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2018.10.030 |
| Popis: | Let G be a connected graph. A configuration of pebbles assigns a nonnegative integer number of pebbles to each vertex of G . A move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if any vertex can get at least one pebble through a sequence of moves. The pebbling number of G , denoted π ( G ) , is the smallest integer such that any configuration of π ( G ) pebbles on G is solvable. A graph has the two-pebbling property if after placing more than 2 π ( G ) − q pebbles on G , where q is the number of vertices with pebbles, there is a sequence of moves so that at least two pebbles can be placed on any vertex. A graph has the odd-two-pebbling property if after placing more than 2 π ( G ) − r pebbles on G , where r is the number of vertices with an odd number of pebbles, there is a sequence of moves so that at least two pebbles can be placed on any vertex. In this paper, we prove that the two-pebbling and odd-two-pebbling properties are not equivalent. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect