i need the number of pebbles for a cycle graph with 4 vertices
I think, the pebbling number of C_4 should be 4.
Let C_4 = ({v_1, v_2, v_3, v_4},{{v_1, v_2}, {v_2, v_3}, {v_3, v_4}, {v_4, v_1}) be our representation of the cycle graph with 4 vertices, and lets call (p_1, p_2, p_3, p_4) a (pebble) configuration of C_4 with p_i pebbles on v_i. Without loss of generality we assume that we want to put a pebble on v_1. To do so, we need 2 pebbles on either v_2 or v_4. Any starting configuration that puts 2 or more pebbles on v_2 or v_4 is therefore solvable, and of course those that start with a pebble on v_1 are solvable too. Therefore we consider the configuration (0,1,2,1), so no pebble on v_1, one pebble on v_2 and v_4, and two pebbles on v_3, which is the only configuration with 4 pebbles that does not satisfy the conditions above. Removing the two pebbles from v_3 and adding one to v_2 (or v_4, both work), then removing two from v_2 (or v_4) and adding one to v_1 also solves this configuration. Therefore, all configurations of 4 pebbles on C_4 can be solved.
Now to show that the pebbling number cannot be 3: The configuration (0,0,3,0) can be played to (0,1,1,0) or (0,0,1,1), and in both cases one is stuck, so it must be higher than 3.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs