Nov. 27 (10:00-11:00) room C.714
Anna Khmelnitskaya (Saint-Petersburg State University)
The number of ways to construct a connected graph: a graph-based generalization of the binomial coefficients
The topic of this paper does not relate directly to the game theory, but the interest for this study was strongly influenced by our study of Shapley-type solution concepts for cooperative games with limited cooperation introduced by means of communication graphs. If there are no restrictions on cooperation, the classical Shapley value assigns to each player, as a payoff, the average of the player’s marginal contributions with respect to all possible orderings of the players. However, in cooperative games endowed with a communication graph not all orderings of the players are feasible since only connected players are able to cooperate. We evaluate a player communication ability in a connected graph through the number of ways the graph can be constructed starting with this player and adding successively players adjacent to those already added before. When the graph is a path on n + 1 vertices, these numbers are exactly the binomial coefficients in row n of Pascal’s triangle. Hence, for other connected graphs, these numbers, called the connectivity degrees of the vertices, generalize the binomial coefficients. We show that the connectivity degrees have properties that for paths reduce to well-known properties of the binomial coefficients. We obtain an explicit formula representation of the connectivity degree that straightforwardly generalizes the binomial coefficient formula. We show that when the number of vertices in a graph minus one is prime, the connectivity degree of every cut vertex is divisible by this prime. Furthermore, the connectivity degree of a vertex is equal to the sum of this vertex connectivity degrees in all subgraphs obtained by deleting precisely one of the non-cut vertices of the graph. Similar to the binomial coefficients in a row of Pascal’s triangle, in a tree the ratio of the connectivity degrees of every two adjacent vertices is equal to the ratio of the numbers of vertices in two subgraphs resulting from deleting the edge between these vertices. For arbitrary connected graph the latter is true only when an edge is a bridge, the deletion of which splits the graph into two components. We also prove that the connectivity degrees of the vertices in a tree, when normalized to sum up to one, are equal to the steady state probabilities of some Markov chain on the vertices of the graph. Furthermore, on a connected graph the connectivity degrees of its vertices can be seen as a measure of centrality. On the class of trees we provide an axiomatic characterization of this connectivity centrality measure.
The talk is based on joint work with Gerard van der Laan and Dolf Talman.