The Number of Ways to Construct a Connected Graph: A Graph-Based

Generalization of the Binomial Coefficients

Anna Khmelnitskaya Faculty of Applied Mathematics Saint Petersburg State University

Universitetskii prospekt 35 Petergof, Saint Petersburg 198504

Russia

a.b.khmelnitskaya@utwente.nl

Gerard van der Laan

School of Business and Economics and Tinbergen Institute

Vrije Universiteit Amsterdam De Boelelaan 1105 1081 HV Amsterdam The Netherlands

  gerardl280651@gmail.com

Dolf Talman

CentER, Department of Econometrics & Operations Research Tilburg University Warandelaan 2 5037 AB Tilburg The Netherlands

talman@tilburguniversity.edu

Abstract 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.

1 Introduction

The study of binomial coefficients has a long history of more than two thousand years and many interpretations are known. Recently we investigated solution concepts for cooperative games endowed with a communication structure on the set of players represented by a graph based on the idea that only players connected in the graph are able to cooperate. The communication ability of a player in a connected graph was evaluated through the number of ways the graph can be constructed starting with this player and adding successively players adjacent to those already added before. These numbers of communication ability led to a new interpretation of the binomial coefficients. It turns out that when a communication structure on a set of n+1 players is represented by a path from player 0 to player n, for player k this number is exactly equal to the binomial coefficient \binom{n}{k}. Whence for connected graphs the communication ability numbers, further called connectivity degrees of the vertices, can be seen as a generalization of the binomial coefficients. Moreover, it turned out that for arbitrary connected graphs these numbers possess properties that for paths reduce to wellknown properties of the binomial coefficients. This came really as a nice and unexpected surprise. But since everything is just lying on the surface and the proofs of the properties are very simple and straightforward, we were not sure whether this might be something new and still unknown.

A thorough search through the literature shows that there exists indeed a number of publications, which in one or another way interpret or generalize the binomial coefficients and study either some specific properties of the binomial coefficients or more sophisticated mathematical objects having similarities or common features with them. For example, Fontené [4] generalizes binomial coefficients, replacing the natural numbers by an arbitrary sequence A_{n} of real or complex numbers. For A_{n} = n these generalized binomial coefficients are the ordinary binomial coefficients, for A_{n} = q^{n} − 1 they recover the q-binomial coefficients, also called Gaussian binomial coefficients, and as Gould [5] notes, for the sequence of Fibonacci numbers the Fibonomial coefficients are obtained. Leroy, Rigo, and Stipulanti [6] introduce a generalization of Pascal’s triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Loeb [7] studies a generalization of the binomial coefficients induced by some generalization of the factorials. Dash [2] considers relations between graph colorings and binomial coefficients. However, no publication concerning some generalization or extension of the binomial coefficients in terms of connectivity degrees of the vertices in a connected graph or some other equivalent notion has been found.

The results obtained in this paper are quite attractive and promising, and they find nice applications in different applied studies. For instance, the connectivity degrees of the vertices provide a measure of centrality on a connected graph, which is an important tool in studying social networks. Also they appear in formulas providing explicit representations of solutions for cooperative games with restricted cooperation represented by means of an undirected communication graph. Cooperative games with restricted cooperation, in particular, may be used for the evaluation of a political power distribution among a group of political parties when it is needed to take into account abilities of the parties to communicate with each other in reaching consensus and making joint decisions. Besides, 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. Applied to paths this gives another new interpretation of the binomial coefficients.

In this paper we study as a generalization of the binomial coefficients the connectivity degrees of the vertices in simple connected graphs. We obtain an explicit formula representation of the connectivity degree of a vertex in a connected graph via the connectivity degrees of the adjacent vertices in the connected subgraphs resulting from deleting all edges containing the vertex. This straightforwardly generalizes the binomial coefficient formula. As a corollary, this formula provides that when the number of vertices in a graph minus one is a prime number, then, similar to the binomial coefficients, the connectivity degree of every cut vertex is divisible by this prime. We also show that, like the binomial coefficients, the connectivity degree of a vertex is equal to the sum of the connectivity degrees of this vertex in all subgraphs obtained by deleting precisely one of the non-cut vertices of the graph. Moreover, similar to the binomial coefficients in any 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 the two subgraphs resulting from deleting the edge between these vertices. For an arbitrary connected graph the latter is true only if the edge is a bridge, the deletion of which splits the graph in two components. We also prove that in a tree the connectivity degrees, when normalized to sum up to 1, are the steady state probabilities of a Markov chain (cf. Norris [8]), in which at any vertex the process moves to an adjacent vertex with a probability proportional to the number of vertices connected to the vertex through this adjacent vertex. The Ehrenfest model (cf. P. Ehrenfest and T. Ehrenfest [3]), a classical physics model to study the properties of thermodynamic equilibrium, evolves a Markov chain having the same steady state probabilities as the ones on a path. Furthermore, the connectivity degrees of the vertices in a connected graph can be seen as a measure of centrality (cf. Borgatti and Everett [1]). On the class of trees we provide an axiomatic characterization of this connectivity centrality measure.

The structure of the paper is as follows. Some well-known definitions and properties of the binomial coefficients and graphs are recalled in Section 2. Section 3 introduces the notion of connectivity degree of the vertices in a connected graph and proves that for a path the connectivity degrees coincide with a row of Pascal’s triangle. Section 4 shows that on connected graphs the connectivity degrees possess properties that on paths reduce to the properties of the binomial coefficients discussed in Sections 2 and 3. Section 5 proves that on a tree the connectivity degrees when normalized to sum up to 1 are the steady state probabilities of some Markov chain. Section 6 considers the connectivity degrees as a centrality measure and provides its axiomatic characterization on the class of trees.

2 Preliminaries

2.1 Binomial coefficients

For all integers n ≥ 0 and 0 ≤ k ≤ n, the binomial coefficient \binom{n}{k} is equal to the number of ways to choose k from n elements,

\binom{n}{k} = \frac{n!}{(n − k)! k!}.  (1)

Arranging the binomial coefficients in successive rows for n = 0, 1, 2, … in a triangular array gives Pascal’s triangle (\underline{A007318} in Sloane et al. [9]), see Figure 1.

1 1 17 16 1521 1415 1310 35 12620 1310 35 1415 1521 16 71 1 1

Figure 1: The first eight rows of Pascal’s triangle.

For integers n ≥ 1 and 0 ≤ k ≤ n, formula (1) implies the recurrence relation

\binom{n}{k} = \binom{n − 1}{k − 1} + \binom{n − 1}{k},  (2)

where \binom{n−1}{k−1} = 0 if k = 0 and \binom{n−1}{k} = 0 if k = n. If n is a prime number, from (1) it also follows that \binom{n}{k} is divisible by this prime for k = 1, …, n − 1. For n ≥ 1, (1) further implies the ratio property

\begin{matrix}( & {n \atop k} & ) \\ ( & {n \atop k+1} & ) \end{matrix} = \frac{k + 1}{n − k} ,  k = 0, …, n − 1,  (3)

where, in row n of Pascal’s triangle, k + 1 is the number of positions from k to the left and n − k the number of positions from k + 1 to the right. Moreover, for n ≥ 1,

∑_{k=0}^{n}(−1)^{k}\binom{n}{k} = (1 + (−1))^{n} = 0.  (4)

For integers n ≥ 0 and 0 ≤ k ≤ n, let (n, k) denote position k in row n of Pascal’s triangle. It is well-known that the binomial coefficient \binom{n}{k} is equal to the number of paths in Pascal’s triangle that start at the apex (0, 0) and terminate at position (n, k), when at every step a path moves diagonally to the next row either to the left or to the right. Conversely, the number of paths in Pascal’s triangle starting at (n, k) and moving at each step diagonally upwards either to the left or to the right until the apex is reached, is also equal to \binom{n}{k}.

2.2 Graphs and permutations

A (simple) graph is a pair (V, E) consisting of a finite nonempty set V of vertices and a set E ⊆ {{v, w} | v, w ∈ V, v ≠ w} of edges. A graph (V, E) is connected if |V | = 1 or for every v, w ∈V, v ≠ w, there is a path in (V, E) between v and w, i.e., for some k ≥ 1 there exists a sequence of edges {v_{h}, v_{h+1}} ∈ E, h = 1, …, k, such that v_{1} = v and v_{k+1} = w. The set of all connected graphs is denoted by G. For S ⊆ V, a graph (S, E|_{S}) with E|_{S} = {e ∈ E | e ⊆ S} is the subgraph of (V, E) induced by S. The set S is connected in (V, E) if (S, E|_{S}) is connected. The collection of maximal connected subsets of S in (V, E), called the components of S in (V, E), is denoted by S/E. The (unique) element in S/E containing v ∈ S is denoted by (S/E)_{v} and the (unique) element in S/E containing {v, w} ∈ E|_{S} is denoted by (S/E)_{vw}. For ease of notation, the set V \{v} is denoted by V_{−v}, E|_{V_{−v}} by E_{−v}, and E\{{v, w}} by E_{−vw}.

A connected graph (V, E) is a tree if for every v, w ∈ V, v ≠ w, there exists a unique path in (V, E) between v and to w. The set of all trees is denoted by T . A graph (V, E) is bipartite if V can be partitioned into two sets V_{1} and V_{2} such that every edge in E is composed by one vertex in V_{1} and one in V_{2}. Every tree is a bipartite graph. If {v, w} ∈ E, then w is adjacent to v in (V, E). The set of vertices adjacent to v ∈ V in (V, E) is denoted by B_{v}^{E}, and d_{v}(V, E) = |B_{v}^{E}| is the degree of v in (V, E). A vertex v ∈ V is a leaf in (V, E) if d_{v}(V, E) = 1. A tree (V, E) is a path if d_{v}(V, E) ≤ 2 for all v ∈ V. An edge {v, w} ∈ E is a bridge in (V, E) if (V/E)_{vw} is disconnected in (V, E_{−vw}). A connected graph (V, E) is a tree if and only if every edge in E is a bridge. A vertex v ∈ V is a cut vertex in (V, E) if (V/E)_{v} \ {v} is nonempty and disconnected in (V_{−v}, E_{−v}). The set of non-cut vertices in a graph (V, E) is denoted by S(V, E). Every leaf in a graph is a non-cut vertex and in a tree on two or more vertices every non-cut vertex is a leaf. An element in V_{−v}/E, v ∈ V, is a satellite of v in (V, E). When (V, E) is a tree, every satellite of a vertex v in (V, E) contains exactly one vertex adjacent to v in (V, E).

A permutation of V is a sequence π = (π_{1}, …, π_{|V |}) of the elements of V. For a connected graph (V, E) and v ∈ V, a permutation π of V is admissible with respect to v in (V, E) if π_{1} = v and for j = 2, …, |V | the set {π_{1}, …, π_{j}} is connected in (V, E). The set of permutations of V admissible with respect to v in (V, E) is denoted by Π_{v}^{E}(V) and let c_{v}(V, E) = |Π_{v}^{E}(V)|.

3 Connectivity degrees and binomial coefficients on paths

In this section we introduce the notion of the connectivity degree of a vertex in a connected graph and show that on paths the connectivity degrees coincide with the binomial coefficients.

In an arbitrary connected graph the number of permutations admissible with respect to some vertex is equal to the number of ways the graph can be constructed starting at the vertex by successive adding at each step a vertex adjacent to at least one of those already added before, or equivalently, the number of ways non-cut vertices can be removed from the graph one by one until only this vertex is left. Hence, the numbers of permutations admissible with respect to the vertices in a connected graph reflect the ability of each vertex to initiate a successive connective creation of the graph. Therefore we call these numbers connectivity degrees.

Definition 1. For a connected graph (V, E), the connectivity degree of vertex v ∈ V in (V, E) is given by the number c_{v}(V, E).

Let (V, E) be a path. Without loss of generality we may assume that V = {v_{0}, …, v_{n}} and E = {{v_{0}, v_{1}}, …, {v_{n−1}, v_{n}}} for some integer n ≥ 0. Then the connectivity degrees of the vertices in (V, E) are equal to the binomial coefficients on row n of Pascal’s triangle. Indeed, for each 0 ≤ k ≤ n, the number c_{v_{k}}(V, E) by definition is equal to the number of sequences starting at vertex v_{k} and obtained by successive adding vertices adjacent either to the left or to the right end of those added before, in total k times to the left and n − k times to the right, i.e.,

c_{v_{k}}(V, E) = \frac{n!}{(n − k)! k!}.

This together with equality (1) yields the following theorem.

Theorem 2. Let (V, E) be a path with V = {v_{0}, …, v_{n}} and E = {{v_{0}, v_{1}}, …, {v_{n−1}, v_{n}}} for some integer n ≥ 0. Then, for integer 0 ≤ k ≤ n,

c_{v_{k}}(V, E) = \binom{n}{k}.  (5)

Theorem 2 implies that for 0 ≤ k ≤ n the binomial coefficient \binom{n}{k} is equal to the number of ways the path (V, E) can be constructed starting at vertex v_{k} by successive adding vertices adjacent to one of the vertices added before, or equivalently, to the number of ways the noncut vertices can be removed from the path one by one until only vertex v_{k} is left. Furthermore, this also implies that for n ≥ 0 the total number of ways a path on n + 1 vertices can be constructed starting at any vertex is equal to 2^{n} (\underline{A000079} in Sloane et al. [9]).

Next, for a path (V, E) with V = {v_{0}, …, v_{n}} and E = {{v_{0}, v_{1}}, …, {v_{n−1}, v_{n}}}, n ≥ 1, consider the subpaths (V_{−v_{0}}, E_{−v_{0}}) and (V_{−v_{n}}, E_{−v_{n}}) obtained by deleting the non-cut vertices v_{0} and v_{n}, respectively. All permutations of V admissible with respect to v ∈ V in (V, E) can be partitioned disjointly into those which end with v_{0} and those which end with v_{n}. A permutation (π_{1}, …, π_{|V |−1}, v_{0}) of V with π_{1} = v, v ≠ v_{0}, is admissible with respect to v in (V, E) if and only if permutation (π_{1}, …, π_{|V |−1}) of V_{−v_{0}} is admissible with respect to v in (V_{−v_{0}}, E_{−v_{0}}). The latter keeps valid if we replace v_{0} by v_{n}. Wherefrom, by letting c_{v_{0}}(V_{−v_{0}}, E_{−v_{0}}) = 0 and c_{v_{n}}(V_{−v_{n}}, E_{−v_{n}}) = 0, we obtain immediately the next result.

Theorem 3. Let (V, E) be a path with V = {v_{0}, …, v_{n}} and E = {{v_{0}, v_{1}}, …, {v_{n−1}, v_{n}}} for some integer n ≥ 1. Then, for integer 0 ≤ k ≤ n,

c_{v_{k}}(V, E) = c_{v_{k}}(V_{−v_{0}}, E_{−v_{0}}) + c_{v_{k}}(V_{−v_{n}}, E_{−v_{n}}).  (6)

Theorem 3 provides the recurrence relation (6) for the connectivity degrees of the vertices in a path, which reflects the recurrence relation (2) for binomial coefficients. It states that the connectivity degree of a vertex in a path is equal to the sum of the connectivity degrees of this vertex in the two subpaths obtained by deleting one of the two non-cut vertices. Figure 2 illustrates Theorem 3 for n = 7 showing that the connectivity degree of a vertex in the lower path (V, E) is equal to the sum of the connectivity degrees of this vertex in the upper path (V_{−v_{0}}, E_{−v_{0}}) and the middle path (V_{−v_{7}}, E_{−v_{7}}).

[figure: 1; 6; 15; 20; 15; 6; 1; 0; 0; 1; 6; 15; 20; 15; 6; 1; v_{0}; v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; v_{7}; 1; 7; 21; 35; 35; 21; 7; 1]

Figure 2: Illustration of Theorem 3 for n = 7.

4 Connectivity degrees on connected graphs

In this section we show that properties of the connectivity degrees of the vertices in connected graphs generalize the properties of binomial coefficients discussed in the previous two sections, and therefore the connectivity degrees of the vertices in connected graphs can be seen as a generalization of the binomial coefficients.

The first theorem generalizes Theorem 2 for binomial coefficients on paths and relates the connectivity degree of a vertex in a connected graph to the connectivity degrees of the adjacent vertices in the subgraphs induced by the satellites of the vertex. Since in a connected graph (V, E) the satellites of a vertex v ∈ V form a partition of V_{−v} and |V_{−v}| = |V | − 1, the multinomial coefficient

\binom{|V | − 1}{|C|, C ∈ V_{−v}/E} = \frac{(|V | − 1)!}{∏_{C∈V_{−v}/E}|C|!}

is well defined.

For a connected graph (V, E), v ∈ V, and C ∈ V_{−v}/E, define the extended subgraph of (V, E) induced by C with respect to v by the graph (C, E_{C}^{v}) on C with

E_{C}^{v} = E|_{C} ∪ {{u, w} | u, w ∈ B_{v}^{E} ∩ C, u ≠ w, {u, w} ∉ E},

in which for every two distinct vertices in C adjacent to v the edge containing these vertices, when not in E, is added to E|_{C}. Note that E_{C}^{v} = E|_{C} if (V, E) is a tree, since in a tree every vertex has only one adjacent vertex in each of its satellites.

Theorem 4. Let (V, E) be a connected graph and v ∈ V. Then

c_{v}(V, E) = \begin{cases}1, & if |V | = 1; \\ \binom{|V |−1}{|C|, C∈V_{−v}/E} ∏_{C∈V_{−v}/E} ∑_{w∈B_{v}^{E}∩C} c_{w}(C, E_{C}^{v}), & if |V | ≥ 2. \end{cases}  (7)

In particular, when (V, E) is a tree,

c_{v}(V, E) = \begin{cases}1, & if |V | = 1; \\ \binom{|V |−1}{|(V_{−v}/E)_{w}|, w∈B_{v}^{E}} ∏_{w∈B_{v}^{E}}c_{w}((V_{−v}/E)_{w}, E|_{(V_{−v}/E)_{w}}), & if |V | ≥ 2. \end{cases}  (8)

Proof. Clearly, c_{v}(V, E) = 1 if V = {v}. Suppose |V | ≥ 2. Since (V, E) is a connected graph on at least two vertices, we have that v has at least one neighbor in (V, E). Therefore, V_{−v}/E ≠ ∅ and B_{v}^{E} ∩ C ≠ ∅ for all C ∈ V_{−v}/E.

First, v is only adjacent in (V, E) to the vertices in B_{v}^{E}∩C for each C ∈ V_{−v}/E. Therefore, a permutation π belongs to Π_{v}^{E}(V) if and only if π_{1} = v and for every C ∈ V_{−v}/E the subpermutation of π on C, π|_{C}, is admissible with respect to some vertex w ∈ B_{v}^{E} ∩ C in the extended subgraph (C, E_{C}^{v}). The consideration of the extended subgraph (C, E_{C}^{v}) instead of (C, E|_{C}) is due to the fact that if C contains also vertices adjacent to v other than w, these vertices can be at any position in π|_{C} because they are connected to w via v. Thus, for each C ∈ V_{−v}/E, the number of permutations of C that are subpermutations of permutations in Π_{v}^{E}(V) is equal to

∑_{w∈B_{v}^{E}∩C} c_{w}(C, E_{C}^{v}).

Second, every permutation of V obtained from π ∈ Π_{v}^{E}(V) by replacing π|_{C} for some C ∈ V_{−v}/E by another permutation admissible with respect to a vertex w ∈ B_{v}^{E} ∩ C in (C, E_{C}^{v}) is also a permutation in Π_{v}^{E}(V), which explains the product in formula (7).

Third, since the satellites of v in (V, E) are not connected to each other, vertices of different satellites are unordered concerning admissibility with respect to v. Therefore, the number of permutations π ∈ Π_{v}^{E}(V), that for all C ∈ V_{−v}/E have the same π|_{C}, is equal to the number of partitions of a set of |V | − 1 elements into sets of size |C|, C ∈ V_{−v}/E. This is precisely the multinomial coefficient in formula (7).

If (V, E) is a tree, then every satellite of a vertex v ∈ V in (V, E) is equal to (V_{−v}/E)_{w} for some unique w ∈ B_{v}^{E} and formula (7) reduces to (8).

Remark 5. For a path the multinomial coefficients in formula (8) are binomial coefficients, because every vertex has (at most) two satellites. Moreover, for every vertex the connectivity degree of each adjacent vertex in the subgraph induced by the satellite containing this adjacent vertex is equal to 1. Hence, for a path formula (8) reduces to (5).

If v is a non-cut vertex in a connected graph (V, E) with |V | ≥ 2, then V_{−v} is the unique satellite of v in (V, E), and, in particular, when v is a leaf, then also E_{V_{−v}}^{v} = E_{−v}.

Corollary 6. If v is a non-cut vertex in a connected graph (V, E) with |V | ≥ 2, then

c_{v}(V, E) = ∑_{w∈B_{v}^{E}} c_{w}(V_{−v}, E_{V_{−v}}^{v}).

In particular, if v is a leaf and w ∈ V is the unique adjacent to v vertex in (V, E), then c_{v}(V, E) = c_{w}(V_{−v}, E_{−v}).

If v ∈ V is a cut vertex in a connected graph (V, E), then v is a non-cut vertex in the subgraph induced by C_{+v} = C ∪ {v} for every C ∈ V_{−v}/E, and Theorem 4 and Corollary 6 imply the next corollary.

Corollary 7. If v is a cut vertex in a connected graph (V, E), then

c_{v}(V, E) = \binom{|V | − 1}{|C|, C ∈ V_{−v}/E} ∏_{C∈V_{−v}/E} c_{v}(C_{+v}, E|_{C_{+v}}).

From the last two corollaries the prime number property immediately follows.

Corollary 8. For a connected graph (V, E) with |V | − 1 being a prime number, the connectivity degree of every cut vertex is divisible by this prime. Moreover, when (V, E) is a tree, the connectivity degrees of all leaves are not divisible by this prime.

Note that in a graph with cycles the connectivity degree of a non-cut vertex can be divisible by this prime. For example, if (V, E) is the complete graph, then every vertex is a non-cut vertex and its connectivity degree is equal to (|V | − 1)!.

Theorem 4 together with Corollaries 6 and 7 shows that the connectivity degree of a vertex in a connected graph can be calculated via the connectivity degrees of its adjacent vertices in smaller subgraphs and for cut vertices also alternatively via the connectivity degrees of the vertex itself in smaller subgraphs.

Example 9. Consider the graph (V, E) depicted in Figure 3. For cut vertex v_{2}, by Theo-

[figure: v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; v_{7}; v_{8}]

Figure 3: The graph (V, E) of Example 9.

rem 4,

c_{v_{2}}(V, E) = \binom{7}{1, 5, 1} c_{v_{1}}(\{v_{1}\}, E|_{\{v_{1}\}}) · c_{v_{3}}(V′, E′) · c_{v_{7}}(\{v_{7}\}, E|_{\{v_{7}\}}),

where V′ = {v_{3}, v_{4}, v_{5}, v_{6}, v_{8}} and E′ = E|_{V′}. Clearly, c_{v_{1}}({v_{1}}, E|_{{v_{v_{1}}}}) = c_{v_{7}}({v_{7}}, E|_{{v_{7}}}) = 1, and for the leaf v_{3} in (V′, E′) Corollary 6 implies c_{v_{3}}(V′, E′) = c_{v_{4}}(V′_{−v_{3}}, E′_{−v_{3}}) = 3, because (V′_{−v_{3}}, E′_{−v_{3}}) is a path. Hence,

c_{v_{2}}(V, E) = \frac{7!}{1! 5! 1!} · 1 · 3 · 1 = 126.

Similarly, for cut vertex v_{4},

c_{v_{4}}(V, E) = \binom{7}{4, 2, 1} c_{v_{3}}(V′′, E′′) · c_{v_{5}}(\{v_{5}, v_{6}\}, E|_{\{v_{5},v_{6}\}}) · c_{v_{8}}(\{v_{8}\}, E|_{\{v_{8}\}}),

where V′′ = {v_{1}, v_{2}, v_{3}, v_{7}} and E′′ = E|_{V′′}. Since c_{v_{5}}({v_{5}, v_{6}}, E|_{{v_{5},v_{6}}})=c_{v_{8}}({v_{8}}, E|_{{v_{8}}})=1 and for the leaf v_{3} in (V′′, E′′) Corollary 6 implies c_{v_{3}}(V′′, E′′)=c_{v_{2}}(V′′_{−v_{3}}, E′′_{−v_{3}})=2, we have

c_{v_{4}}(V, E) = \frac{7!}{4! 2! 1!} · 2 · 1 · 1 = 210.

For leaf v_{1},

c_{v_{1}}(V, E) = c_{v_{2}}(V_{−v_{1}}, E_{−v_{1}}) = \binom{6}{5} c_{v_{3}}(V′, E′) · c_{v_{7}}(\{v_{7}\}, E|_{\{v_{7}\}}) = 6 · 3 · 1 = 18.

Note that both c_{v_{2}}(V, E) = 126 and c_{v_{4}}(V, E) = 210 are divisible by the prime number |V | − 1 = 7 and that c_{v_{1}}(V, E) = 18 is not divisible by 7, as also follows from Corollary 8.

Example 10. Let (V, E) be a star with V = {v_{0}, …, v_{n}} and E = {{v_{0}, v_{1}}, …, {v_{0}, v_{n}}} for some n ≥ 0. From Theorem 4 it follows that for the hub v_{0},

c_{v_{0}}(V, E) = n!,

(\underline{A000142} in Sloane et al. [9]), because for |V | = 1 we have n = 0 and n! = 1, and for |V | > 1 we have B_{v_{0}}^{E} = V_{−v_{0}} and (V_{−v_{0}}/E)_{v_{k}} = {v_{k}} for all 1 ≤ k ≤ n. Further, since each vertex v_{k}, 1 ≤ k ≤ n, is a leaf connected to the hub v_{0} and the subgraph induced by V_{−v_{k}} is a star on n vertices, Corollary 6 implies that for 1 ≤ k ≤ n,

c_{v_{k}}(V, E) = c_{v_{0}}(V_{−v_{k}}, E_{−v_{k}}) = (n − 1)!.

This also implies that for n ≥ 1 the total number of ways to construct a star on n+1 vertices starting from any vertex is equal to 2n! (\underline{A052849} in Sloane et al. [9]).

Next, let (V, E) be a generalized star with V = {v_{0}, …, v_{n}}, n ≥ 0, in which for some 1 ≤ k ≤ n the vertices v_{1}, …, v_{k} are adjacent to the hub v_{0} and each subgraph induced by (V_{−v_{0}}/E)_{v_{h}}, 1 ≤ h ≤ k, is a path with n_{h} ≥ 1 vertices and having v_{h} as its leaf when n_{h} > 1. Then c_{v_{h}}((V_{−v_{0}}/E)_{v_{h}}, E|_{(V_{−v_{0}}/E)_{v_{h}}}) = 1 for all 1 ≤ h ≤ k, and ∑_{h=1}^{k} n_{h} = n. From Theorem 4 it follows that

c_{v_{0}}(V, E) = \binom{n}{n_{1}, …, n_{k}}.

Therefore, in a generalized star the connectivity degree of the hub is equal to the multinomial coefficient for the sizes of its satellites.

Example 11. Let (V, E) be a cycle graph with the set of vertices V = {v_{1}, …, v_{n}} and the set of edges E = {{v_{0}, v_{1}}, …, {v_{n−1}, v_{n}}, {v_{n}, v_{1}}}, n ≥ 3. We prove by induction on n that c_{v}(V, E) = 2^{n−2} (\underline{A000079} in Sloane et al. [9]) for all v ∈ V. Let v = v_{k} for some 1 ≤ k ≤ n. Since (V, E) is a cycle graph, we have that v is a non-cut vertex in (V, E) and B_{E}^{v} = {v_{k−1}, v_{k+1}}, where v_{k−1} = v_{n} if k = 1 and v_{k+1} = v_{1} if k = n. From Corollary 6 it follows that

c_{v}(V, E) = c_{v_{k−1}}(V_{−v}, E_{V_{−v}}^{v}) + c_{v_{k+1}}(V_{−v}, E_{V_{−v}}^{v}),  (9)

where E_{V_{−v}}^{v} = {{v_{k−1}, v_{k+1}}} for n = 3 and E_{V_{−v}}^{v} = E_{−v} ∪ {{v_{k−1}, v_{k+1}}} for n > 3. If n = 3, then (V_{−v}, E_{V_{−v}}^{v}) is a path on 2 vertices, and, by Theorem 2, equality (9) implies

c_{v}(V, E) = 1 + 1 = 2 = 2^{n−2}.

Next, let n > 3 and assume that for all cycle graphs on at least 3 and at most n − 1 vertices the assertion holds. Since (V_{−v}, E_{V_{−v}}^{v}) is a cycle graph on n − 1 vertices, equality (9) implies

c_{v}(V, E) = 2^{n−3} + 2^{n−3} = 2^{n−2}.

The latter equality also implies that for n ≥ 3 the total number of ways to construct a cycle graph on n vertices starting from any vertex is equal to n2^{n−2} (\underline{A057711} in Sloane et al. [9]).

The next theorem generalizes the ratio property (3) for binomial coefficients and states that in a connected graph the ratio between the connectivity degrees of any two adjacent vertices connected by a bridge is equal to the ratio of the numbers of vertices in the two subgraphs resulting from deleting the bridge between these two vertices.

Theorem 12. Let (V, E) be a connected graph and {v, w} a bridge in (V, E). Then

\frac{c_{v}(V, E)}{c_{w}(V, E)} = \frac{|(V/E_{−vw})_{v}|}{|(V/E_{−vw})_{w}|}.

Proof. For ease of notation, let C_{v} = (V/E_{−vw})_{v} and C_{w} = (V/E_{−vw})_{w}. Since (V, E) is a connected graph and {v, w} is a bridge in (V, E), we have that C_{v} and C_{w} are the two components of V in (V, E_{−vw}). Therefore, for every π ∈ Π_{v}^{E}(V) the subpermutation π|_{C_{w}} is admissible with respect to w in (C_{w}, E|_{C_{w}}) and for every π ∈ Π_{w}^{E}(V) the subpermutation π|_{C_{v}} is admissible with respect to v in (C_{v}, E|_{C_{v}}). Since C_{v} and C_{w} are not connected to each other in (V, E_{−vw}), this implies

c_{v}(V, E) = \binom{|V | − 1}{|C_{v}| − 1} c_{v}(C_{v}, E|_{C_{v}}) · c_{w}(C_{w}, E|_{C_{w}})  (10)

and

c_{w}(V, E) = \binom{|V | − 1}{|C_{w}| − 1} c_{w}(C_{w}, E|_{C_{w}}) · c_{v}(C_{v}, E|_{C_{v}}).

Hence, since |C_{v}| + |C_{w}| = |V |,

\frac{c_{v}(V, E)}{c_{w}(V, E)} = \frac{(|V | − 1)!/((|C_{v}| − 1)!|C_{w}|!)}{(|V | − 1)!/((|C_{w}| − 1)!|C_{v}|!)} = \frac{|C_{v}|}{|C_{w}|} = \frac{|(V/E_{−vw})_{v}|}{|(V/E_{−vw})_{w}|}.

In a tree every edge is a bridge, so for a tree Theorem 12 holds for every pair of adjacent vertices. Hence, if in a tree the connectivity degree of one vertex is known, one can calculate successively the connectivity degrees of the others. Furthermore, by Theorem 2, for a path Theorem 12 reduces to the ratio property (3) for binomial coefficients. Remark 13. Formula (10) provides an alternative way to calculate the connectivity degrees of the vertices connected by a bridge via their connectivity degrees in smaller subgraphs.

Theorem 12 implies the next corollary.

Corollary 14. If in a connected graph deleting a bridge splits the graph in two subgraphs with equal numbers of vertices, the connectivity degrees of both vertices joined by the bridge are equal.

Note that in Pascal’s triangle we indeed have that \binom{n}{k−1} = \binom{n}{k} for odd n and k = \frac{1}{2}(n+1).

Example 15. Consider again the graph (V, E) in Figure 3. In Example 9 we found that c_{v_{4}}(V, E) = 210. Since the deletion of the bridge {3, 4} yields two subgraphs with four vertices in each, from Corollary 14 it follows that

c_{v_{3}}(V, E) = c_{v_{4}}(V, E) = 210.

Next, by Theorem 12,

c_{v_{2}}(V, E) = \frac{3}{5} c_{v_{3}}(V, E) = 126,

which was also found before. Continuing this way we find

c_{v_{1}}(V, E) = c_{v_{7}}(V, E) = \frac{1}{7}c_{v_{2}}(V, E) = 18,
c_{v_{5}}(V, E) = \frac{2}{6} c_{v_{4}}(V, E) = 70,
c_{v_{6}}(V, E) = \frac{1}{7} c_{v_{5}}(V, E) = 10,
c_{v_{8}}(V, E) = \frac{1}{7} c_{v_{4}}(V, E) = 30.

Figure 4 depicts the connectivity degrees of all vertices in (V, E).

[figure: 18; 126; 210; 210; 70; 10; 18; 30]

Figure 4: The connectivity degrees for the graph in Figure 3.

The next theorem generalizes the well-known recurrence relation (2) for binomial coefficients and therefore extends Theorem 3 from paths to connected graphs. The theorem states that the connectivity degree of a vertex in a connected graph is equal to the sum of the connectivity degrees of this vertex in all subgraphs obtained by deleting from the graph one of the non-cut vertices.

Theorem 16. Let (V, E), |V | ≥ 2, be a connected graph and v ∈ V. Then

c_{v}(V, E) = ∑_{w∈S(V,E)} c_{v}(V_{−w}, E_{−w}),

where c_{w}(V_{−w}, E_{−w}) = 0 for all w ∈ S(V, E).

Proof. The result follows from the fact that every permutation of V admissible with respect to v in (V, E) ends with some w ∈ S(V, E). The proof strategy is similar to that in the proof of Theorem 3.

Figure 5 illustrates Theorem 16 by the decomposition of the connectivity degrees of the vertices in a connected graph with three non-cut vertices, where the numbers represent the connectivity degrees of the vertices, with zero for the non-cut vertex deleted from the graph.

[figure: 3; 6; 2; 3; =; 1; 2; 1; 0; +; 0; 2; 1; 1; +; 2; 2; 0; 2]

Figure 5: Illustration of Theorem 16.

Theorem 16 gives another iterative procedure for finding connectivity degrees by starting the calculation in subgraphs of smaller size and increasing successively their sizes.

Example 17. Consider again the cycle graph (V, E) from Example 11 and compute c_{v}(V, E), v ∈ V, by applying Theorem 16. Since each vertex in V is a non-cut vertex in (V, E), i.e., S(V, E) = V, for v ∈ V we obtain from Theorem 16,

c_{v}(V, E) = ∑_{w∈V_{−v}} c_{v}(V_{−w}, E_{−w}).

Each subgraph (V_{−w}, E_{−w}), w ∈ V, is a path on n − 1 vertices, and for every v ∈ V and integer 0 ≤ k ≤ n − 2 there exists a unique w ∈ V_{−v} satisfying c_{v}(V_{−w}, E_{−w}) = \binom{n−2}{k}. Hence, for every v ∈ V,

c_{v}(V, E) = ∑_{k=0}^{n−2} \binom{n − 2}{k} = 2^{n−2},

as also obtained in Example 11.

Theorem 16 implies also the following theorem that generalizes formula (4) for the binomial coefficients.

Theorem 18. Let (V, E), |V | ≥ 2, be a connected graph and s = (s_{v})_{v∈V} be a sign vector satisfying s_{v}s_{w} = −1 for all {v, w} ∈ E. Then

∑_{v∈V} s_{v}c_{v}(V, E) = 0.

Proof. The proof is by induction on |V |. If V = {v, w}, then c_{v}(V, E) = c_{w}(V, E) = 1, and therefore c_{v}(V, E)−c_{w}(V, E) = 0. Next, let |V | > 2 and assume that for all connected graphs on at least 2 and at most |V | − 1 vertices the assertion holds. For each w ∈ S(V, E) we have that (V_{−w}, E_{−w}) is a connected graph on |V | − 1 vertices and s_{u}s_{v} = −1 for all {u, v} ∈ E_{−w}. From the induction hypothesis we obtain that for every w ∈ S(V, E),

∑_{v∈V} s_{v}c_{v}(V_{−w}, E_{−w}) = 0,

where c_{w}(V_{−w}, E_{−w}) = 0. From Theorem 16 it follows that

∑_{v∈V} s_{v}c_{v}(V, E) = ∑_{v∈V} s_{v} ∑_{w∈S(V,E)} c_{v}(V_{−w}, E_{−w}) = ∑_{w∈S(V,E)} ∑_{v∈V} s_{v}c_{v}(V_{−w}, E_{−w}) = 0.

Remark 19. A sign vector satisfying the condition of Theorem 18 exists if and only if the graph is bipartite, i.e., the graph has no cycles of odd length. Therefore, for a tree and, in particular, a path such a sign vector always exists.

Theorem 18 is illustrated in Figure 6, where the numbers sum up to zero.

[figure: 18; −126; 210; −210; 70; −10; 18; 30]

Figure 6: Illustration of Theorem 18 for the graph in Figure 3.

5 Connectivity degrees and steady state probabilities

In this section we show that for a tree by normalizing the sum of the connectivity degrees of its vertices to 1, one gets the steady state probabilities of a Markov chain on the set of its vertices as the states.

First, consider a path (V, E) with V = {v_{0}, …, v_{n}} and E = {{v_{0}, v_{1}}, …, {v_{n−1}, v_{n}}} for some integer n ≥ 1, and let c be the row vector of connectivity degrees on (V, E), i.e., c_{v_{k}} = \binom{n}{k}, k = 0, …, n. Let P = (p_{v_{k}v_{h}})_{k,h=0,...,n} be the (n + 1) × (n + 1) transition matrix on (V, E) given by

p_{v_{k}v_{h}} = \begin{cases}\frac{k}{n}, & if h = k − 1; \\ \frac{n−k}{n}, & if h = k + 1; \\ 0, & otherwise, \end{cases}

i.e., the transition probability from vertex v_{k} to adjacent vertex v_{k−1} (v_{k+1}) is proportional to the number of positions to the left (right) of position k in row n of Pascal’s triangle. The next theorem follows from straightforward calculations.

Theorem 20. Let (V, E) be a path with V ={v_{0}, …, v_{n}} and E ={{v_{0}, v_{1}}, …, {v_{n−1}, v_{n}}}, n ≥ 1. Then cP = c, i.e., for every integer 0 ≤ k ≤ n the normalized binomial coefficient \binom{n}{k}/2^{n} is the steady state probability that the Markov chain on (V, E) with transition matrix P is in vertex v_{k}.

Theorem 20 implies that the binomial coefficients in row n of Pascal’s triangle yield the relative probabilities for the Markov chain with transition matrix P to be in each of the vertices of a path with n + 1 vertices.

Remark 21. The Ehrenfest model (cf. [3]), a discrete model for the exchange of gas molecules between two containers, evolves a Markov chain having the same steady state probabilities.

Next, we show that also for a tree the connectivity degrees of the vertices determine the steady state distribution of some Markov chain. For a given tree (V, E) with |V | ≥ 2, let c = (c_{v}(V, E))_{v∈V} be the |V |-dimensional row vector of connectivity degrees on (V, E) and P = (p_{vw})_{v,w∈V} the |V | × |V | transition matrix on (V, E) given by

p_{vw} = \begin{cases}\frac{|(V_{−v}/E)_{w}|}{|V |−1}, & if \{v, w\} ∈ E; \\ 0, & otherwise, \end{cases}  (11)

i.e., the transition probability from vertex v to adjacent vertex w is proportional to the size of the satellite of v in (V, E) containing w. The following theorem generalizes Theorem 20 for the binomial coefficients to the connectivity degrees of the vertices in trees.

Theorem 22. Let (V, E) be a tree with |V | ≥ 2. Then cP = c, i.e., for every v ∈ V the normalized connectivity degree c_{v}(V, E)/ ∑_{w∈V} c_{w}(V, E) is the steady state probability that the Markov chain on (V, E) with transition matrix P defined in (11) is in vertex v.

Proof. Since (V, E) is a tree, we have (V_{−w}/E)_{v} = (V/E_{−vw})_{v} and (V_{−v}/E)_{w} = (V/E_{−vw})_{w}. Therefore, Theorem 12 implies that for every w ∈ B_{v}^{E},

|(V_{−w}/E)_{v}|c_{w}(V, E) = |(V_{−v}/E)_{w}|c_{v}(V, E).

Since ∑_{w∈B_{v}^{E}} |(V_{−v}/E)_{w}| = |V | − 1, after summation over w ∈ B_{v}^{E} we obtain

∑_{w∈B_{v}^{E}} |(V_{−w}/E)_{v}|c_{w}(V, E) = (|V | − 1)c_{v}(V, E).

Dividing both sides by |V | − 1 yields ∑_{w∈B_{v}^{E}} c_{w}p_{wv} = c_{v}, which completes the proof.

Remark 23. It is easy to verify that for a connected graph (V, E) with |V | ≥ 2 we have dP′ = d, where d = (d_{v}(V, E))_{v∈V} and P′ = (p′_{vw})_{v,w∈V} is the |V | × |V | transition matrix on (V, E) given by

p′_{vw} = \begin{cases}1/d_{v}(V, E), & if \{v, w\} ∈ E; \\ 0, & otherwise. \end{cases}

Therefore, the degrees of the vertices of an arbitrary connected graph, when normalized to sum equal to 1, are the steady state probabilities of a Markov chain in which at every vertex the process moves with equal probability to each of its adjacent vertices.

6 Connectivity degrees as centrality measure

For a connected graph each permutation of vertices admissible with respect to some vertex induces a way of successive connective construction of the graph starting at this vertex, which gives grounds to consider the connectivity degrees of the vertices in a connected graph as a measure of centrality. Centrality is a fundamental concept in network analysis and centrality measures answer the question which vertices in a graph under scrutiny are important, cf. Borgatti and Everett [1].

A centrality measure is a function f on the set of connected simple graphs G that assigns to every (V, E) ∈ G a vector f(V, E) = (f_{v}(V, E))_{v∈V}, where f_{v}(V, E) measures the centrality of v ∈ V in (V, E). A well-known centrality measure is the degree measure assigning to a connected graph the vector of degrees of its vertices. We define the connectivity centrality measure as the function c on G that assigns to every (V, E) ∈ G the vector of connectivity degrees of its vertices c(V, E) = (c_{v}(V, E))_{v∈V}. The properties and examples above in fact support this definition. Indeed, if {v, w} ∈ E is a bridge in (V, E) ∈ G and component (V/E_{−vw})_{v} has more vertices than component (V/E_{−vw})_{w}, it is quite natural to consider vertex v to have a more central position in the graph than w, and this is just reflected by the inequality c_{v}(V, E) > c_{w}(V, E), as follows from Theorem 12. As shown by Example 10, the connectivity centrality of the hub in a star with n + 1 vertices is n times larger than that of each of the n non-cut vertices. Also Figures 2 and 4 depicting graphs together with the connectivity degrees of their vertices visually demonstrate that the closer a vertex to the center is, the higher is its connectivity degree.

In the literature it is quite standard to characterize centrality measures by their properties (axioms). It is easy to see that the connectivity centrality measure meets the next three axioms.

Single vertex normalization: A centrality measure f on G satisfies single vertex normalization if f_{v}(V, E) = 1 when V = {v}.

Because in a singleton (connected) graph there is just one vertex, the axiom emphasizes the importance of this vertex, assigning to it a positive measure normalized to 1. Remark 24. The degree measure does not satisfy single vertex normalization, because the degree of a vertex in a graph on one vertex is zero. It seems natural that such a singleton vertex is of importance and has a positive measure.

The ratio property: A centrality measure f on G satisfies the ratio property if for every (V, E) ∈ G and bridge {v, w} in (V, E),

\frac{f_{v}(V, E)}{f_{w}(V, E)} = \frac{|(V/E_{−vw})_{v}|}{|(V/E_{−vw})_{w}|}.

To the best of our knowledge the ratio property does not hold for any centrality measure known in the literature, nevertheless it seems to be rather natural. The axiom states that the centralities of two vertices connected by a bridge are proportional to the sizes of the resulting after deletion of the bridge components containing these vertices.

Leaf consistency: A centrality measure f on G satisfies leaf consistency if for every (V, E) ∈ G and leaf v in (V, E), we have f_{v}(V, E) = f_{w}(V_{−v}, E_{−v}), where w is the unique vertex in (V, E) adjacent to v.

Consistency properties are quite usual in the literature on the characterization of functions, for instance, in the theory of solutions for cooperative games. Here the axiom states that a leaf is as central in a graph as its unique adjacent vertex is central in the subgraph without the leaf.

On the class of trees T the connectivity centrality measure can be characterized by these three axioms.

Theorem 25. The connectivity centrality measure is the unique centrality measure on the class of trees that meets single vertex normalization, the ratio property, and leaf consistency.

Proof. The proof is by induction on |V |. Let f on T satisfy the three properties. First, single vertex normalization implies f_{v}(V, E) = 1 = c_{v}(V, E) if V = {v}. Next, let (V, E) ∈ T with |V | > 1 and assume that the three axioms uniquely determine the connectivity degrees of each tree on at most |V | − 1 vertices. Since (V, E) is a tree and |V | ≥ 2, we have that (V, E) has at least one leaf v. Let w be the unique vertex in (V, E) adjacent to v. By leaf consistency and the induction hypothesis, f_{v}(V, E) = c_{w}(V_{−v}, E_{−v}). From Corollary 6 it follows that f_{v}(V, E) = c_{v}(V, E). By repeated application of the ratio property we may determine f_{w}(V, E) for every w ≠ v. Since f_{v}(V, E) = c_{v}(V, E), Theorem 12 implies that f_{w}(V, E) = c_{w}(V, E) for all w ≠ v, which completes the proof.

Note that in the proof the determination of f_{w}(V, E), w ∈ V, is independent of the choice of the leaf v. The result of Theorem 25 is not extendable to a class of connected graphs that also may contain cycles. For example, each centrality measure on a subclass G′ ⊆ G satisfying G′ ⊋ T , defined on T as the connectivity centrality measure c and on G′ \ T as αc for some real α ≠ 0, meets all three axioms, since G′ \ T contains only graphs with at least three vertices and (V_{−v}, E_{−v}) ∈ G′ \ T whenever (V, E) ∈ G′ \ T and v is a leaf in (V, E).

7 Acknowledgment

The authors would like to thank René van den Brink, Pavel Chebotarev, Dinard van der Laan, Mánuel Mágó, Jacco Thijssen, and two anonymous reviewers for their helpful remarks and suggestions. The result in Theorem 18 was pointed out to the authors by Mánuel Mágó. The research of Anna Khmelnitskaya was supported by RFBR (Russian Foundation for Basic Research) grant #16-01-00713 and NWO (Dutch Organization of Scientific Research) grant #040.11.516. Her research was done partially during her stay at Vrije Universiteit Amsterdam and University of Twente, the hospitality of both universities is highly appreciated.

References

[1] S. P. Borgatti and M. G. Everett, A graph-theoretic perspective on centrality, Social Networks 28 (2006), 466–484.

[2] D. Dash, Distributed Resource Allocation with Local Information, Doctoral thesis, Rice University, 2013.

[3] P. Ehrenfest and T. Ehrenfest, Über eine Aufgabe aus der Warscheinlichkeitsrechnung die mit der kinetischen Deutung der Entropievermehrung zusammenhängt, Mathematisch Naturwissenschaftliche Blätter 3 (1906), 128.

[4] G. Fontené, Généralisation d’une formule connue, Nouv. Ann. Math. 15 (1915), 112.

[5] H. W. Gould, The bracket function and Fontené-Ward generalized binomial coefficients with application to Fibonomial coefficients, Fibonacci Quart. 7 (1969), 23–40, 55.

[6] J. Leroy, M. Rigo, and M. Stipulanti, Generalized Pascal triangle for binomial coefficients of words, Adv. in Appl. Math. 80 (2016), 24–47.

[7] D. E. Loeb, A generalization of the binomial coefficients, Discrete Math. 105 (1992), 143–156.

[8] J. R. Norris, Markov Chains, Cambridge University Press, 1997.

[9] N. J. A. Sloane et al., On-line Encyclopedia of Integer Sequences, https://oeis.org, 2022.

2020 Mathematics Subject Classification: Primary 05A10; Secondary 05C05, 11B65, 60J10, 91A43. Keywords: binomial coefficient, Pascal’s triangle, connected graph, Markov chain, centrality measure.

(Concerned with sequences \underline{A000079}, \underline{A000142}, \underline{A007318}, \underline{A052849}, and \underline{A057711}.)

Received November 15 2022; revised version received March 31 2023. Published in Journal of Integer Sequences, April 8 2023.

Return to Journal of Integer Sequences home page.