Graph Pebbling on Graphs as Moving Resources in a Network
First let us establish the basics of Graph Pebbling and then once that is understood we will explain how to interpret this with respect to moving resources in a network. In the standard sense, a graph is a pair G=(V,E) where V is the vertex set and E is the edge set. We will restrict our attention to connected simple graphs. Connected means that for any v1, v2 in the vertex set there exists an edge path in G connecting v1 to v2. Simple means that for distinct v1 and v2 there is at most one edge connecting them and there are no edges from a vertex v to itself. So from now on all graphs will be simple and connected. Now we “place” pebbles on each vertex of the graph. It is easier to imagine this as actually placing pebbles on a reach set of vertices and edges but we may also think of it as an unfaithful labeling of the vertices (unfaithful in this context meaning that two vertices may be labeled with the same number of pebbles). We are free to place any finite number of pebbles on any vertex; this includes placing no pebbles on some vertex. Now we will describe a “pebbling move”. Let v1 and v2 be two adjacent vertices in G. Let v1 have n pebbles on it and v2 have m pebbles on it. Then a pebbling move from v1 to v2 removes two pebbles from v1 and adds one to v2. So the end result is n-2 pebbles on v1 and m+1 pebbles on v2. An importance aspect of repeating pebbling is that each pebbling move decreases the total number of pebbles on the graph by one and so successive pebbling moves will eventually terminate — there being no more possible pebbling moves. We can never have negative pebbles on a vertex so for a vertex to pebble, it must have at least two pebbles on it; hence, this is where the terminating of pebbling moves comes from. There are then different aspects of graphs with regard to pebbling that we want to consider. Let G be a graph. Then we define p(G) to be the smallest natural number n such that for any vertex v of G and any distribution of n pebbles on the vertices of G, there exists a sequence of pebbling moves that results with at least one pebble on vertex v. Note that since we must account for ANY distribution of the n pebbles, this is not nearly a trivial as placing a single pebble on each vertex. One easy example is if G is a complete graph then p(G) is precisely the number of vertices of G. This is because for any vertex, either it has a pebble on it, or it is connected to a vertex with two pebbles on it since all vertices are connected. To see that this is minimal we may consider placing one pebble on |V|-1 of the vertices and then no pebbling sequence can get a pebble to the remaining vertex.
Now let us consider how these graphs and graph pebbling relates to networks and moving resources. We are familiar with a graph representing a network such as in friendship graphs and such. One example that will nicely relate to graph pebbling is train routes. Let G=(V,E) be a graph where the vertex set is comprised of some cities in the US. Then let two vertices be adjacent in G if there exists a train route from one city to the other. We will assume for now that trains can go both ways. Obviously, we can choose remote enough cities such that this graph G is not connected but let us suppose that we have chosen in such a way that this does not occur. So G is a connected graph. Then G is simple since we do not add multiple edges between cities depending on the number of routes on if a route between the cities exist or not. Furthermore we may just limit our graph G to not include any edges from a a vertex to itself. So G is a simple, connected graph as we saw before. In this network, we are considering that each city has some resource that is will be sending to other cities. The number of pebbles on each vertex will represent a relative worth of the resources they have. Now recalling that a pebbling move subtracts one pebble from the total number of pebbles on the graph, this can be explained by the fact that the cost of transporting resources is non-zero. So a pebbling move, which represents moving resources, is not without cost. So now we have established a clear connection between the more abstract graph pebbling and the much more concrete moving of resources in a network. Note that of course we’ve only given one example of how we can see graph pebbling as moving resources in a network but hopefully it is clear how other networks and other versions of pebbles mirror this relationship. Now let us think of the importance of p(G) for our city network graph G. Perhaps to make it more realistic let us think that each vertex is a location of some company building that we will call COMPANY and the edges are still the train routes between the cities the COMPANY buildings are in. If COMPANY wants to be reliable but minimize cost via inventory limitation it will want to be able to have its product available at any of its locations when needed. Hence, p(G) is an important factor for COMPANY to consider. So if COMPANY has p(G) of its product spread out across the vertices (its locations) then if a customer comes to any location, COMPANY can use the train routes to move its product to the location the customer is at.
Although this is not the focus of this blog post we should mention that graph pebbling can also be seen through a game theory perspective. Again we start with a graph G and a pebbling distribution on the vertices of G. Then two players A and B will take turn making pebbling moves. Whoever makes a pebbling move such that no more pebbling moves are possible loses the game. This is not by any means a simple game since in most pebbling distributions, at any point in the game, each player will have multiple choices. Hence, the strategy for winning is a complicated function depending on each choice they and their opponent make. But there are some things we will recognize such as dominated strategies. For example let G be a graph where |V|-2 vertices have one pebble on them, one vertex v1 has two pebbles on it and one vertex v2 has zero pebbles on it. Suppose that v1 and v2 are adjacent and that v1 is adjacent to at least one of the |V|-2 vertices with one pebble on them. For a player to choose to pebble from v1 to v2 is clearly a dominated strategy since they automatically lose. Although they may lose anyway (some games are not dependent on the players’ choices but who makes the first move) making this pebbling move is a guaranteed loss and thus should not be chosen.
https://arxiv.org/pdf/math/0406024.pdf
https://en.wikipedia.org/wiki/Graph_pebbling