The Number of Ways to Construct a Connected Graph: A Graph-Based Generalization of the Binomial Coefficients

This paper studies the number of ways a given connected simple graph can be constructed by a sequence of expanding connected subgraphs starting with a given vertex. 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 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.