\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm
{\LARGE\bf
\bf The Number of Ways to Construct a \\
\vskip .01in
Connected Graph: A Graph-Based
\vskip .1in
Generalization of the Binomial Coefficients}
\vskip 0.8cm
\large
Anna Khmelnitskaya\\Faculty of Applied Mathematics\\Saint Petersburg State University\\Universitetskii prospekt 35\\ Petergof, Saint Petersburg 198504\\Russia\\
{\href{mailto:a.b.khmelnitskaya@utwente.nl}{\tt 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\\
{\href{mailto:gerardl280651@gmail.com}{\tt gerardl280651@gmail.com}}\\
\ \\
Dolf Talman\\CentER, Department of Econometrics \& Operations Research\\Tilburg University\\Warandelaan 2\\5037 AB Tilburg\\The Netherlands\\
{\href{mailto:talman@tilburguniversity.edu}{\tt talman@tilburguniversity.edu}}
\end{center}
\vskip .2in
\begin{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.
\end{abstract}
\section{Introduction}\label{intro section}
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 ${n\choose 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 well-known 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\'e~\cite{fontene} 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~\cite{gould} notes, for the sequence of Fibonacci numbers the Fibonomial coefficients are obtained.
Leroy, Rigo, and Stipulanti~\cite{leroy-rigo-stipulanti} 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~\cite{loeb} studies a generalization of the binomial coefficients induced by some generalization of the factorials.
Dash~\cite{dash} 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~\cite{norris}), 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~\cite{ehrenfest}), 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~\cite{borgatti-everett}).
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~\ref{Sect:preliminaries}.
Section~\ref{Sect:paths} 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~\ref{Sect:graphs} shows that on connected graphs the connectivity degrees possess properties that on paths reduce to the properties of the binomial coefficients discussed in Sections~\ref{Sect:preliminaries} and \ref{Sect:paths}.
Section~\ref{Sect:Markov} 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~\ref{Sect:axiom} considers the connectivity degrees as a centrality measure and provides its axiomatic characterization on the class of trees.
\section{Preliminaries}
\label{Sect:preliminaries}
\subsection{Binomial coefficients}
\label{Subsection:bincoeff}
For all integers $n\geq 0$ and $0\leq k\leq n$, the \emph{binomial coefficient} $n\choose k$ is equal to the number of ways to choose $k$ from $n$ elements,
\begin{equation}\label{def-binomial}
{n\choose k}=\frac{n!}{(n-k)!\,k!}.
\end{equation}
Arranging the binomial coefficients in successive rows for $n=0,1,2,\ldots$ in a triangular array gives \emph{Pascal's triangle} ({\seqnum{A007318}} in Sloane  et al.~\cite{sloane}), see Figure~\ref{fig:Pascal}.
\begin{figure}[ht]
\centering
\setlength{\unitlength}{1mm}
\begin{picture}(20,25)(8,4)
\put(-35,-20){$1$}
\put(-27.5,-14){$1$}
\put(-20,-8){$1$}\put(-20,-20){$7$}
\put(-12.5,-2){$1$}\put(-12.5,-14){$6$}
\put(-5,4){$1$}\put(-5,-8){$5$}\put(-5,-20){$21$}
\put(2.5,10){$1$}\put(2.5,-2){$4$}\put(2.5,-14){$15$}
\put(10,16){$1$}\put(10,4){$3$}\put(10,-8){$10$}\put(10,-20){$35$}
\put(17.5,22){$1$}\put(17.5,10){$2$}\put(17.5,-2){$6$}\put(17.5,-14){$20$}
\put(25,16){$1$}\put(25,4){$3$}\put(25,-8){$10$}\put(25,-20){$35$}
\put(32.5,10){$1$}\put(32.5,-2){$4$}\put(32.5,-14){$15$}
\put(40,4){$1$}\put(40,-8){$5$}\put(40,-20){$21$}
\put(47.5,-2){$1$}\put(47.5,-14){$6$}
\put(55,-20){$7$}\put(55,-8){$1$}
\put(62.5,-14){$1$}
\put(70,-20){$1$}
\end{picture}
\vspace{27mm}
\caption{The first eight rows of Pascal's triangle.}
\label{fig:Pascal}
\end{figure}

For integers $n\geq 1$ and $0\leq k\leq n$, formula (\ref{def-binomial}) implies the recurrence relation
\begin{equation}\label{binomial}
{n\choose k} = {n-1\choose k-1} + {n-1\choose k},
\end{equation}
where ${n-1\choose k-1}= 0$ if $k=0$ and ${n-1\choose k}=0$ if $k=n$.
If $n$ is a prime number, from (\ref{def-binomial}) it also follows that ${n\choose k}$ is divisible by this prime for $k=1,\ldots,n-1$.
For $n\geq 1$, (\ref{def-binomial}) further implies the ratio property
\begin{equation}\label{ratio}
\frac{{n\choose k}}{{n\choose k+1}}=\frac{k+1}{n-k},\qquad k=0,\ldots,n-1,
\end{equation}
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\geq 1$,
\begin{equation}\label{zero}
\sum_{k=0}^n(-1)^k{n\choose k}=\big(1+(-1)\big)^n=0.
\end{equation}

For integers $n\geq 0$ and $0\le k\le n$, let $(n,k)$ denote position $k$ in row $n$ of Pascal's triangle.
It is well-known that the binomial coefficient $n\choose 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 $n\choose k$.
\subsection{Graphs and permutations}
\label{Subsection:graphs+perm}
A \emph{(simple) graph} is a pair $(V,E)$ consisting of a finite nonempty set $V$ of \emph{vertices} and a set $E\subseteq\{\{v,w\}\!\mid\!v,w\!\in\!V,v\!\ne\!w\}$ of \emph{edges}.
A graph $(V,E)$ is \emph{connected} if $|V|\!=\!1$ or for every $v,w\!\in\!V$, $v\ne w$, there is a \emph{path} in $(V,E)$ between $v$ and $w$, i.e., for some $k\geq 1$ there exists a sequence of edges $\{v_h,v_{h+1}\}\in E$, $h=1,\ldots,k$, such that $v_1=v$ and $v_{k+1}=w$.
The set of all connected graphs is denoted by ${\cal G}$.
For $S\subseteq V$, a graph $(S,E|_S)$ with $E|_S=\{e\in E\mid e\subseteq S\}$ is the \emph{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 \emph{components} of $S$ in $(V,E)$, is denoted by $S/E$.
The (unique) element in $S/E$ containing $v\in S$ is denoted by $(S/E)_v$ and the (unique) element in $S/E$ containing $\{v,w\}\in E|_S$ is denoted by $(S/E)_{vw}$.
For ease of notation, the set $V\backslash\{v\}$ is denoted by $V_{-v}$, $E|_{V_{-v}}$ by $E_{-v}$, and $E\backslash\{\{v,w\}\}$ by $E_{-vw}$.

A connected graph $(V,E)$ is a \emph{tree} if for every $v,w\in V$, $v\ne w$, there exists a unique path in $(V,E)$ between $v$ and to $w$.
The set of all trees is denoted by ${\cal T}$.
A graph $(V,E)$ is \emph{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\}\in E$, then $w$ is \emph{adjacent} to $v$ in $(V,E)$.
The set of vertices adjacent to $v\in V$ in $(V,E)$ is denoted by $B^E_v$, and $d_v(V,E)=|B^E_v|$ is the \emph{degree} of $v$ in $(V,E)$.
A vertex $v\in V$ is a \emph{leaf} in $(V,E)$ if $d_v(V,E)=1$.
A tree $(V,E)$ is a \emph{path} if $d_v(V,E)\le 2$ for all $v\in V$.
An edge $\{v,w\}\in E$ is a \emph{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\in V$ is a \emph{cut vertex} in $(V,E)$ if $(V/E)_v\setminus\{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\in V$, is a \emph{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 \emph{permutation} of $V$ is a sequence $\pi=(\pi_1,\ldots,\pi_{|V|})$ of the elements of $V$.
For a connected graph $(V,E)$ and $v\in V$, a permutation $\pi$ of $V$ is \emph{admissible with respect to $v$} in $(V,E)$ if $\pi_1=v$ and for $j=2,\ldots,|V|$ the set $\{\pi_1,\ldots, \pi_j\}$ is connected in $(V,E)$.
The set of permutations of $V$ admissible with respect to $v$ in $(V,E)$ is denoted by $\Pi^E_v(V)$ and let $c_v(V,E)=|\Pi^E_v(V)|$.
\section{Connectivity degrees and binomial coefficients on paths}
\label{Sect: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.
\begin{definition}\label{Pascal-numbers}
For a connected graph $(V,E)$, the \emph{connectivity degree} of vertex $v \in V$ in $(V,E)$ is given by the number $c_v(V,E)$.
\end{definition}
Let $(V,E)$ be a path.
Without loss of generality we may assume that $V=\{v_0,\ldots,v_n\}$ and $E=\{\{v_0,v_1\},\ldots,\{v_{n-1},v_n\}\}$ for some integer $n\geq 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\le k\le 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 (\ref{def-binomial}) yields the following theorem.
\begin{theorem}\label{Paths}
Let $(V,E)$ be a path with $V\!=\!\{v_0,\ldots,v_n\}$ and $E\!=\!\{\{v_0,v_1\},\ldots,\{v_{n-1},v_n\}\}$ for some integer $n\geq 0$.
Then, for integer $0\leq k\leq n$,
\begin{equation}\label{paths}
c_{v_k}(V,E)={n\choose k}.
\end{equation}
\end{theorem}
Theorem~\ref{Paths} implies that for $0\leq k\leq n$ the binomial coefficient $n\choose 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 non-cut vertices can be removed from the path one by one until only vertex $v_k$ is left.
Furthermore, this also implies that for $n\geq0$ the total number of ways a path on $n+1$ vertices can be constructed starting at any vertex is equal to $2^n$ ({\seqnum{A000079}} in Sloane  et al.~\cite{sloane}).

Next, for a path $(V,E)$ with $V=\{v_0,\ldots,v_n\}$ and $E=\{\{v_0,v_1\},\ldots,\{v_{n-1},v_n\}\}$, $n\geq1$, 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\in V$ in $(V,E)$ can be partitioned disjointly into those which end with $v_0$ and those which end with $v_n$.
A permutation $(\pi_1,\ldots,\pi_{|V|-1},v_0)$ of $V$ with $\pi_1=v$, $v\ne v_0$, is admissible with respect to $v$ in $(V,E)$ if and only if permutation $(\pi_1,\ldots,\pi_{|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.
\begin{theorem}\label{Decomp}
Let $(V,E)$ be a path with $V\!=\!\{v_0,\ldots,v_n\}$ and $E\!=\!\{\{v_0,v_1\},\ldots,\{v_{n-1},v_n\}\}$ for some integer $n\geq 1$.
Then, for integer $0\leq k\leq n$,
\begin{equation}\label{dec}
c_{v_k}(V,E)=c_{v_k}(V_{-v_0},E_{-v_0})+c_{v_k}(V_{-v_n},E_{-v_n}).
\end{equation}
\end{theorem}
Theorem~\ref{Decomp} provides the recurrence relation (\ref{dec}) for the connectivity degrees of the vertices in a path, which reflects the recurrence relation (\ref{binomial}) 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~\ref{fig:path} illustrates Theorem~\ref{Decomp} 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})$.
\begin{figure}[ht]
\centering
\setlength{\unitlength}{1mm}
\begin{picture}(30,25)(5,0)
\put(-50,0){\circle*{2}}
\put(-30,0){\circle*{2}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(30,0){\circle*{2}}
\put(50,0){\circle*{2}}
\put(70,0){\circle*{2}}
\put(90,0){\circle{1.8}}
\put(-50,0.2){\line(1,0){19.00}}
\put(-30,0.2){\line(1,0){19.00}}
\put(-10,0.2){\line(1,0){19.00}}
\put(10,0.2){\line(1,0){19.00}}
\put(30,0.2){\line(1,0){19.00}}
\put(50,0.2){\line(1,0){19.00}}
\put(-51,4){$1$}
\put(-30.9,4){$6$}
\put(-12,4){$15$}
\put(8,4){$20$}
\put(28,4){$15$}
\put(49.5,4){$6$}
\put(69.2,4){$1$}
\put(89.2,4){$0$}
\put(-50.2,9.7){\circle{1.8}}
\put(-30,10){\circle*{2}}
\put(-10,10){\circle*{2}}
\put(10,10){\circle*{2}}
\put(30,10){\circle*{2}}
\put(50,10){\circle*{2}}
\put(70,10){\circle*{2}}
\put(90,10){\circle*{2}}
\put(-30,10){\line(1,0){19.00}}
\put(-10,10){\line(1,0){19.00}}
\put(10,10){\line(1,0){19.00}}
\put(30,10){\line(1,0){19.00}}
\put(50,10){\line(1,0){19.00}}
\put(70,10){\line(1,0){19.00}}
\put(-51,13.7){$0$}
\put(-31,14){$1$}
\put(-10.6,14){$6$}
\put(8,14){$15$}
\put(28,14){$20$}
\put(48,14){$15$}
\put(69.3,14){$6$}
\put(89,14){$1$}
\put(-50,-15){\circle*{2}}
\put(-30,-15){\circle*{2}}
\put(-10,-15){\circle*{2}}
\put(10,-15){\circle*{2}}
\put(30,-15){\circle*{2}}
\put(50,-15){\circle*{2}}
\put(70,-15){\circle*{2}}
\put(90,-15){\circle*{2}}
\put(-50,-14.8){\line(1,0){19.00}}
\put(-30,-14.8){\line(1,0){19.00}}
\put(-10,-14.8){\line(1,0){19.00}}
\put(10,-14.8){\line(1,0){19.00}}
\put(30,-14.8){\line(1,0){19.00}}
\put(50,-14.8){\line(1,0){19.00}}
\put(70,-14.8){\line(1,0){19.00}}
\put(-50.8,-20){$v_0$}
\put(-30.8,-20){$v_1$}
\put(-10.8,-20){$v_2$}
\put(9.2,-20){$v_3$}
\put(29.2,-20){$v_4$}
\put(49.2,-20){$v_5$}
\put(69.2,-20){$v_6$}
\put(89.2,-20){$v_7$}
\put(-50.8,-11){$1$}
\put(-30.8,-11){$7$}
\put(-12,-11){$21$}
\put(8,-11){$35$}
\put(28,-11){$35$}
\put(48.8,-11){$21$}
\put(69.2,-11){$7$}
\put(89.2,-11){$1$}
\end{picture}
\vspace{25mm}
\caption{Illustration of Theorem~\ref{Decomp} for $n=7$.}
\label{fig:path}
\end{figure}
\section{Connectivity degrees on connected graphs}
\label{Sect: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~\ref{Paths} 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\in V$ form a partition of $V_{-v}$ and $|V_{-v}|=|V|-1$, the multinomial coefficient

$${|V|-1\choose |C|,\ C\in V_{-v}/E}=\frac{(|V|-1)!}{\prod\limits_{C\in V_{-v}/E}\!|C|!}$$
is well defined.

For a connected graph $(V,E)$, $v\in V$, and $C\in V_{-v}/E$, define the \emph{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 \cup \{\{u,w\}\mid u,w\in B^E_v\cap C,u\neq w,\{u,w\}\notin 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.
\begin{theorem}\label{multi-property}
Let $(V,E)$ be a connected graph and $v\in V$. Then
\begin{equation}\label{multi-formula}
c_v(V,E)=\begin{cases}
 1, & \text{if $|V|=1$;}\\
{|V|-1\choose |C|,\ C\in V_{-v}/E}\prod\limits_{C\in V_{-v}/E} \sum\limits_{w\in B^E_v\cap C}c_w(C,E_C^v), & \text{if $|V|\geq 2$.}
 \end{cases}
\end{equation}
In particular, when $(V,E)$ is a tree,
\begin{equation}\label{c-f multi-formula}
c_v(V,E)=\begin{cases}
1 , & \text{if $|V|=1$;}\\
{|V|-1\choose |(V_{-v}/E)_w|,\ w\in B^E_v}
  \prod\limits_{w\in B^E_v}\!
      c_w((V_{-v}/E)_w,E|_{(V_{-v}/E)_w}), & \text{if $|V|\geq 2$.}
 \end{cases}
\end{equation}
\end{theorem}
\begin{proof}
Clearly, $c_v(V,E)=1$ if $V=\{v\}$. Suppose $|V|\geq2$.
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\ne\emptyset$ and $B^E_v\cap C\ne\emptyset$ for all $C\in V_{-v}/E$.

First, $v$ is only adjacent in $(V,E)$ to the vertices in $B^E_v\cap C$ for each $C\in V_{-v}/E$.
Therefore, a permutation $\pi$ belongs to $\Pi^E_v(V)$ if and only if $\pi_1=v$ and for every $C\in V_{-v}/E$ the subpermutation of $\pi$ on $C$, $\pi|_C$, is admissible with respect to some vertex $w\in B^E_v\cap 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 $\pi|_C$ because they are connected to $w$ via $v$.
Thus, for each $C\in V_{-v}/E$, the number of permutations of $C$ that are subpermutations of permutations
in $\Pi^E_v(V)$ is equal to
$$\sum\limits_{w\in B^E_v\cap C}c_w(C,E_C^v).$$

Second, every permutation of $V$ obtained from $\pi\in\Pi^E_v(V)$ by replacing $\pi|_C$ for some $C\in V_{-v}/E$ by another permutation admissible with respect to a vertex $w\in B^E_v\cap C$ in $(C,E_C^v)$ is also a permutation in $\Pi^E_v(V)$, which explains the product in formula (\ref{multi-formula}).

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 $\pi\in\Pi^E_v(V)$, that for all $C\in V_{-v}/E$ have the same $\pi|_C$, is equal to the number of partitions of a set of $|V|-1$ elements into sets of size $|C|$, $C\in V_{-v}/E$.
This is precisely the multinomial coefficient in formula (\ref{multi-formula}).

If $(V,E)$ is a tree, then every satellite of a vertex $v\in V$ in $(V,E)$ is equal to $(V_{-v}/E)_w$ for some unique $w\in B^E_v$ and formula (\ref{multi-formula}) reduces to (\ref{c-f multi-formula}).
\end{proof}
\begin{remark}
For a path the multinomial coefficients in formula (\ref{c-f multi-formula}) 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~(\ref{c-f multi-formula}) reduces to (\ref{paths}).
\end{remark}
If $v$ is a non-cut vertex in a connected graph $(V,E)$ with $|V|\geq 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}$.
\begin{corollary}\label{cor:non-cut}
If $v$ is a non-cut vertex in a connected graph $(V,E)$ with $|V|\geq 2$, then
\[
c_v(V,E)=\sum_{w\in B^E_v}c_w(V_{-v},E_{V_{-v}}^v).
\]
In particular, if $v$ is a leaf and $w\in V$ is the unique adjacent to $v$ vertex in $(V,E)$, then $c_v(V,E)=c_w(V_{-v},E_{-v})$.
\end{corollary}
If $v\in 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\cup\{v\}$ for every $C\in V_{-v}/E$, and Theorem~\ref{multi-property} and Corollary~\ref{cor:non-cut} imply the next corollary.
\begin{corollary}\label{cor:cut}
If $v$ is a cut vertex in a connected graph $(V,E)$, then
\[
c_v(V,E)={|V|-1\choose |C|,\ C\in V_{-v}/E}
          \prod\limits_{C\in V_{-v}/E}c_v(C_{+v},E|_{C_{+v}}).
\]
\end{corollary}
 From the last two corollaries the prime number property immediately follows.
\begin{corollary}\label{cor:prime} 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.
\end{corollary}
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~\ref{multi-property} together with Corollaries~\ref{cor:non-cut} and \ref{cor:cut} 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.
\begin{example}\label{ex:graph}
Consider the graph $(V,E)$ depicted in Figure~\ref{fig:graph}.
\begin{figure}[ht]
\centering
\setlength{\unitlength}{1mm}
\begin{picture}(30,25)(8,0)
\put(-30,0){\circle*{2}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(30,0){\circle*{2}}
\put(50,0){\circle*{2}}
\put(70,0){\circle*{2}}
\put(-10,15){\circle*{2}}
\put(30,15){\circle*{2}}
\put(-30,0.2){\line(1,0){19.00}}
\put(-10,0.2){\line(1,0){19.00}}
\put(10,0.2){\line(1,0){19.00}}
\put(30,0.2){\line(1,0){19.00}}
\put(50,0.2){\line(1,0){19.00}}
\put(-10,0.2){\line(0,1){13,75}}
\put(30,0.2){\line(0,1){13,75}}
\put(-30.8,-5){$v_1$}
\put(-10.8,-5){$v_2$}
\put(9.2,-5){$v_3$}
\put(29.2,-5){$v_4$}
\put(49.2,-5){$v_5$}
\put(69.2,-5){$v_6$}
\put(-10.8,18){$v_7$}
\put(29.2,18){$v_8$}
\end{picture}
\vspace{5mm}
\caption{The graph $(V,E)$ of Example~\ref{ex:graph}.}
\label{fig:graph}
\end{figure}
For cut vertex $v_2$, by Theorem~\ref{multi-property},
\[
c_{v_2}(V,E)={7\choose 1,5,1}\,
  c_{v_1}(\{v_1\},E|_{\{v_1\}})\cdot c_{v_3}(V',E')\cdot  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~\ref{cor:non-cut} 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!}\cdot 1\cdot 3\cdot 1=126.
\]
Similarly, for cut vertex $v_4$,
\[
c_{v_4}(V,E)={7\choose 4,2,1}\, c_{v_3}(V'',E'')\cdot
    c_{v_5}(\{v_5,v_6\},E|_{\{v_5,v_6\}})\cdot  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~\ref{cor:non-cut} 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!}\cdot 2\cdot 1\cdot 1=210.
\]
For leaf $v_1$,
\[
c_{v_1}(V,E)=c_{v_2}(V_{-v_1},E_{-v_1})={6\choose 5}\ c_{v_3}(V',E')\cdot
 c_{v_7}(\{v_7\},E|_{\{v_7\}})=6\cdot 3\cdot 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~\ref{cor:prime}.
\end{example}
\begin{example}\label{ex:star}
Let $(V,E)$ be a star with $V=\{v_0,\ldots,v_n\}$ and $E=\{\{v_0,v_1\},\ldots,\{v_0,v_n\}\}$ for some $n\geq 0$.
 From Theorem~\ref{multi-property} it follows that for the hub~$v_0$,
\[
c_{v_0}(V,E)=n!,
\]
({\seqnum{A000142}} in Sloane  et al.~\cite{sloane}), because for $|V|=1$ we have $n=0$ and $n!=1$, and for $|V|>1$ we have $B^E_{v_0}=V_{-v_0}$ and $(V_{-v_0}/E)_{v_k}=\{v_k\}$ for all $1\le k\le n$.
Further, since each vertex~$v_k$, $1\le k\le 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~\ref{cor:non-cut} implies that for $1\le k\le n$,
\[
c_{v_k}(V,E)=c_{v_0}(V_{-v_k},E_{-v_k})=(n-1)!.
\]
This also implies that for $n\geq1$ the total number of ways to construct a star on $n+1$ vertices starting from any vertex is equal to $2n!$ ({\seqnum{A052849}} in Sloane  et al.~\cite{sloane}).

Next, let $(V,E)$ be a generalized star with $V=\{v_0,\dots,v_n\}$, $n\geq0$, in which for some $1\leq k \leq n$ the vertices $v_1,\ldots,v_k$ are adjacent to the hub~$v_0$ and each subgraph induced by $(V_{-v_0}/E)_{v_h}$, $1\le h\le k$, is a path with $n_h\geq1$ 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\le h\le k$, and $\sum_{h=1}^k~n_h=n$.
 From Theorem~\ref{multi-property} it follows that
\[
c_{v_0}(V,E)={n\choose n_1,\ldots,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.
\end{example}
\begin{example}\label{ex:cycle}
Let $(V,E)$ be a cycle graph with the set of vertices  $V=\{v_1,\dots,v_n\}$ and the set of edges
$E=\{\{v_0,v_1\},\ldots,\{v_{n-1},v_n\},\{v_n,v_1\}\}$, $n\geq3$.
We prove by induction on $n$ that $c_{v}(V,E)=2^{n-2}$ ({\seqnum{A000079}} in Sloane  et al.~\cite{sloane}) for all $v\in V$.
Let $v=v_k$ for some $1\le k\le n$.
Since $(V,E)$ is a cycle graph, we have that $v$ is a non-cut vertex in $(V,E)$ and $B^{v}_E=\{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~\ref{cor:non-cut} it follows that
\begin{equation}\label{eq:cycle}
c_{v}(V,E)=c_{v_{k-1}}(V_{-v},E_{V_{-v}}^v)+ c_{v_{k+1}}(V_{-v},E_{V_{-v}}^v),
\end{equation}
where $E_{V_{-v}}^v=\{\{v_{k-1},v_{k+1}\}\}$ for $n=3$ and $E_{V_{-v}}^v=E_{-v}\cup\{\{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~\ref{Paths}, equality (\ref{eq:cycle}) 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 (\ref{eq:cycle}) implies
$$c_{v}(V,E)=2^{n-3}+2^{n-3}=2^{n-2}.$$
The latter equality also implies that for $n\geq3$ the total number of ways to construct a cycle graph on $n$ vertices starting from any vertex is equal to $n2^{n-2}$ ({\seqnum{A057711}} in Sloane  et al.~\cite{sloane}).
\end{example}
The next theorem generalizes the ratio property~(\ref{ratio}) 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.
\begin{theorem}\label{ratio-vertices}
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|}.
\]
\end{theorem}
\begin{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 $\pi\in \Pi^E_v(V)$ the subpermutation $\pi|_{C_w}$ is admissible with respect to $w$ in $(C_w,E|_{C_w})$ and for every $\pi\in\Pi^E_w(V)$ the subpermutation $\pi|_{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
\begin{equation}\label{bridge}
c_v(V,E)={|V|-1 \choose |C_v|-1}\ c_v(C_v,E|_{C_v})\cdot  c_w(C_w,E|_{C_w})
\end{equation}
and
\[
c_w(V,E)={|V|-1 \choose |C_w|-1}\ c_w(C_w,E|_{C_w})\cdot  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)!/\Bigl((|C_v|-1)!|C_w|!\Bigr)}{(|V|-1)!/\Bigl((|C_w|-1)!|C_v|!\Bigr)}=
\frac{|C_v|}{|C_w|}=\frac{|(V/E_{-vw})_v|}{|(V/E_{-vw})_w|}.
\]
\end{proof}
In a tree every edge is a bridge, so for a tree Theorem~\ref{ratio-vertices} 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~\ref{Paths}, for a path Theorem~\ref{ratio-vertices} reduces to the ratio property~(\ref{ratio}) for binomial coefficients.
\begin{remark}
Formula~(\ref{bridge}) provides an alternative way to calculate the connectivity degrees of the vertices connected by a bridge via their connectivity degrees in smaller subgraphs.
\end{remark}
Theorem~\ref{ratio-vertices} implies the next corollary.
\begin{corollary}\label{cor:bridge}
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.
\end{corollary}
Note that in Pascal's triangle we indeed have that ${n\choose k-1}={n\choose k}$ for odd $n$ and $k=\frac{1}{2}(n+1)$.
\begin{example}\label{ex:graph-a}
Consider again the graph $(V,E)$ in Figure~\ref{fig:graph}. In Example~\ref{ex:graph} 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~\ref{cor:bridge} it follows that
\[c_{v_3}(V,E)= c_{v_4}(V,E) =210.\]
Next, by Theorem~\ref{ratio-vertices},
\[
c_{v_2}(V,E)=\frac{3}{5}\,c_{v_3}(V,E)=126,
\]
which was also found before. Continuing this way we find
\begin{align*}
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.
\end{align*}
Figure~\ref{fig:degrees} depicts the connectivity degrees of all vertices in $(V,E)$.
\begin{figure}[ht]
\centering
\setlength{\unitlength}{1mm}
\begin{picture}(30,25)(8,0)
\put(-30,0){\circle*{2}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(30,0){\circle*{2}}
\put(50,0){\circle*{2}}
\put(70,0){\circle*{2}}
\put(-10,15){\circle*{2}}
\put(30,15){\circle*{2}}
\put(-30,0.2){\line(1,0){19.00}}
\put(-10,0.2){\line(1,0){19.00}}
\put(10,0.2){\line(1,0){19.00}}
\put(30,0.2){\line(1,0){19.00}}
\put(50,0.2){\line(1,0){19.00}}
\put(-10,0.2){\line(0,1){13,75}}
\put(30,0.2){\line(0,1){13,75}}
\put(-32,-5){$18$}
\put(-13,-5){$126$}
\put(7.7,-5){$210$}
\put(27.5,-5){$210$}
\put(48.3,-5){$70$}
\put(68.5,-5){$10$}
\put(-11.8,18){$18$}
\put(28,18){$30$}
\end{picture}
\vspace{5mm}
\caption{The connectivity degrees for the graph in Figure~\ref{fig:graph}.}
\label{fig:degrees}
\end{figure}
\end{example}
The next theorem generalizes the well-known recurrence relation (\ref{binomial}) for binomial coefficients and therefore extends Theorem~\ref{Decomp} 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.
\begin{theorem}\label{sum-property}
Let $(V,E)$, $|V|\geq 2$, be a connected graph and $v\in V$.
Then
\[
c_v(V,E)=\sum\limits_{w \in S(V,E)}c_v(V_{-w},E_{-w}),
 \]
where $c_w(V_{-w},E_{-w})=0$ for all $w\in S(V,E)$.
\end{theorem}
\begin{proof} The result follows from the fact that every permutation of $V$ admissible with respect to $v$ in $(V,E)$ ends with some $w\in S(V,E)$. The proof strategy is similar to that in the proof of Theorem~\ref{Decomp}.
\end{proof}
Figure~\ref{fig:sum} illustrates Theorem~\ref{sum-property} 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.
\begin{figure}[ht]
\centering
\setlength{\unitlength}{1mm}
\begin{picture}(20,25)(10,0)
\put(-35,0){\circle*{2}}
\put(-20,0){\circle*{2}}
\put(-5,0){\circle*{2}}
\put(-20,14.4){\circle*{2}}
\put(-35,0){\line(1,0){14.00}}
\put(-20,0){\line(1,0){14.00}}
\put(-20,0){\line(0,1){14.40}}
\put(-35,0){\line(1,1){15.00}}
\put(-35.8,-5){$3$}
\put(-20.8,-5){$6$}
\put(-7,-5){$2$}
\put(-21,17){$3$}
\put(15,6){$=$}
\put(40,0){\circle*{2}}
\put(55,0){\circle*{2}}
\put(70,0){\circle*{2}}
\put(55,14.4){\circle{1.8}}
\put(40,0){\line(1,0){14.00}}
\put(55,0){\line(1,0){14.00}}
\put(39.2,-5){$1$}
\put(54.2,-5){$2$}
\put(69.2,-5){$1$}
\put(54.2,17){$0$}
\put(-55,-30){$+$}
\put(-35,-35){\circle{1.8}}
\put(-20,-35){\circle*{2}}
\put(-5,-35){\circle*{2}}
\put(-20,-20){\circle*{2}}
\put(-20,-35){\line(1,0){14.00}}
\put(-20,-35){\line(0,1){14.40}}
\put(-35.8,-40){$0$}
\put(-20.8,-40){$2$}
\put(-6,-40){$1$}
\put(-21,-18){$1$}
\put(15,-30){$+$}
\put(40,-35){\circle*{2}}
\put(55,-35){\circle*{2}}
\put(70,-35){\circle{1.8}}
\put(55,-20.6){\circle*{2}}
\put(40,-35){\line(1,0){14.00}}
\put(55,-35){\line(0,1){14.40}}
\put(40,-35){\line(1,1){15.00}}
\put(39.2,-40){$2$}
\put(54.2,-40){$2$}
\put(69.4,-40){$0$}
\put(54.2,-18){$2$}
\end{picture}
\vspace{41mm}
\caption{Illustration of Theorem~\ref{sum-property}.}
\label{fig:sum}
\end{figure}

Theorem~\ref{sum-property} gives another iterative procedure for finding connectivity degrees by starting the calculation in subgraphs of smaller size and increasing successively their sizes.
\begin{example}\label{ex:cycle-sum}
Consider again the cycle graph $(V,E)$ from Example~\ref{ex:cycle} and compute $c_v(V,E)$, $v\in V$, by applying Theorem~\ref{sum-property}.
Since each vertex in $V$ is a non-cut vertex in $(V,E)$, i.e., $S(V,E)=V$, for $v\in V$ we obtain from Theorem~\ref{sum-property},
\[
c_v(V,E)=\sum\limits_{w \in V_{-v}}c_v(V_{-w},E_{-w}).
\]
Each subgraph $(V_{-w},E_{-w})$, $w\in V$, is a path on $n-1$ vertices, and for every $v\in V$ and integer $0\le k\le n-2$ there exists a unique $w\in V_{-v}$ satisfying $c_v(V_{-w},E_{-w})={n-2\choose k}$.
Hence, for every $v\in V$,
\[
c_v(V,E)=\sum\limits_{k=0}^{n-2}{n-2\choose k}=2^{n-2},
\]
as also obtained in Example~\ref{ex:cycle}.
\end{example}
Theorem~\ref{sum-property} implies also the following theorem that generalizes formula~(\ref{zero}) for the binomial coefficients.
\begin{theorem}\label{zero-theorem}
Let $(V,E)$, $|V|\geq 2$, be a connected graph and $s=(s_v)_{v\in V}$ be a sign vector satisfying $s_v s_w=-1$ for all $\{v,w\}\in E$.
Then
\[
\sum_{v\in V}s_vc_v(V,E)=0.
\]
\end{theorem}
\begin{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\in S(V,E)$ we have that $(V_{-w},E_{-w})$ is a connected graph on $|V|-1$ vertices and $s_us_v=-1$ for all $\{u,v\}\in E_{-w}$.
 From the induction hypothesis we obtain that for every $w\in S(V,E)$,
\[
\sum_{v\in V}s_vc_v(V_{-w},E_{-w})=0,
\]
where $c_w(V_{-w},E_{-w})=0$.
 From Theorem~\ref{sum-property} it follows that
\[
\sum_{v\in V}s_vc_v(V,E)=\sum_{v\in V}s_v\sum_{w \in S(V,E)}c_v(V_{-w},E_{-w})=
\sum_{w \in S(V,E)}\sum_{v\in V}s_vc_v(V_{-w},E_{-w})=0.
\]
\end{proof}
\begin{remark}
A sign vector satisfying the condition of Theorem~\ref{zero-theorem} 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.
\end{remark}
Theorem~\ref{zero-theorem} is illustrated in Figure~\ref{fig:zero}, where the numbers sum up to zero.
\begin{figure}[htb]
\centering
\setlength{\unitlength}{1mm}
\begin{picture}(30,25)(8,0)
\put(-30,0){\circle*{2}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(30,0){\circle*{2}}
\put(50,0){\circle*{2}}
\put(70,0){\circle*{2}}
\put(-10,15){\circle*{2}}
\put(30,15){\circle*{2}}
\put(-30,0.2){\line(1,0){19.00}}
\put(-10,0.2){\line(1,0){19.00}}
\put(10,0.2){\line(1,0){19.00}}
\put(30,0.2){\line(1,0){19.00}}
\put(50,0.2){\line(1,0){19.00}}
\put(-10,0.2){\line(0,1){13,75}}
\put(30,0.2){\line(0,1){13,75}}
\put(-32,-5){$18$}
\put(-15,-5){$-126$}
\put(7.7,-5){$210$}
\put(24.5,-5){$-210$}
\put(48.3,-5){$70$}
\put(65,-5){$-10$}
\put(-11.8,18){$18$}
\put(28,18){$30$}
\end{picture}
\vspace{5mm}
\caption{Illustration of Theorem~\ref{zero-theorem} for the graph in Figure~\ref{fig:graph}.}
\label{fig:zero}
\end{figure}
\section{Connectivity degrees and steady state probabilities}
\label{Sect:Markov}
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,\ldots,v_n\}$ and $E=\{\{v_0,v_1\},\ldots,\{v_{n-1},v_n\}\}$ for some integer $n\geq1$, and let $c$ be the row vector of connectivity degrees on $(V,E)$, i.e., $c_{v_k}={n\choose k}$, $k=0,\ldots,n$.
Let $P=(p_{v_kv_h})_{k,h=0,\ldots,n}$ be the $(n+1)\times(n+1)$ transition matrix on $(V,E)$ given by
\begin{displaymath}
p_{v_kv_h}=\begin{cases}
\frac{k}{n}, & \text{if $h=k-1$};\\
\frac{n-k}{n}, & \text{if $h=k+1$};\\
0, & \text{otherwise},
\end{cases}
\end{displaymath}
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.
\begin{theorem}\label{Markov-ss}
Let $(V,E)$ be a path with $V\!=\!\{v_0,\ldots,v_n\}$ and $E\!=\!\{\{v_0,v_1\},\ldots,\{v_{n-1},v_n\}\}$, $n\geq 1$.
Then $cP=c$, i.e., for every integer $0\le k\le n$ the normalized binomial coefficient ${n\choose k}/2^n$ is the steady state probability that the Markov chain on $(V,E)$ with transition matrix $P$ is in vertex $v_k$.
\end{theorem}
Theorem~\ref{Markov-ss} 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.
\begin{remark}
The Ehrenfest model (cf.\ \cite{ehrenfest}), a discrete model for the exchange of gas molecules between two containers, evolves a Markov chain having the same steady state probabilities.
\end{remark}
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|\geq2$, let $c=(c_v(V,E))_{v\in V}$ be the $|V|$-dimensional row vector of connectivity degrees on $(V,E)$ and $P=(p_{vw})_{v,w\in V}$ the $|V|\times|V|$ transition matrix on $(V,E)$ given by
\begin{equation}\label{pvw}
p_{vw}=\begin{cases}
\frac{|(V_{-v}/E)_w|}{|V|-1}, & \text{if $\{v,w\}\in E$};\\
0, & \text{otherwise},
\end{cases}
\end{equation}
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~\ref{Markov-ss} for the binomial coefficients to the connectivity degrees of the vertices in trees.
\begin{theorem}\label{Markov-theorem}
Let $(V,E)$ be a tree with $|V|\geq2$. Then $cP=c$, i.e., for every $v\in V$ the normalized connectivity degree $c_v(V,E)/\sum_{w\in V}c_w(V,E)$ is the steady state probability that the Markov chain on $(V,E)$ with transition matrix $P$ defined in (\ref{pvw}) is in vertex $v$.
\end{theorem}
\begin{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~\ref{ratio-vertices} implies that for every $w\in B^E_v$,
\[
|(V_{-w}/E)_v|c_w(V,E)=|(V_{-v}/E)_w|c_v(V,E).
\]
Since $\sum_{w\in B^E_v}|(V_{-v}/E)_w|=|V|-1$, after summation over $w\in B^E_v$ we obtain
\[
\sum_{w\in B^E_v}|(V_{-w}/E)_v|c_w(V,E)=(|V|-1)c_v(V,E).
\]
Dividing both sides by $|V|-1$ yields $\sum\limits_{w\in B^E_v}c_wp_{wv}=c_v$, which completes the proof.
\end{proof}
\begin{remark}
It is easy to verify that for a connected graph $(V,E)$ with $|V|\geq2$ we have $dP'=d$, where $d=(d_v(V,E))_{v\in V}$ and $P'=(p'_{vw})_{v,w\in V}$ is the $|V|\times|V|$ transition matrix on $(V,E)$ given by
\begin{displaymath}
p'_{vw}=\begin{cases}
1/d_v(V,E),&\text{if $\{v,w\}\in E$};\\
0,&\text{otherwise}.
\end{cases}
\end{displaymath}
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.
\end{remark}
\section{Connectivity degrees as centrality measure}
\label{Sect:axiom}
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~\cite{borgatti-everett}.

A centrality measure is a function $f$ on the set of connected simple graphs ${\cal G}$ that assigns to every $(V,E)\in{\cal G}$ a vector $f(V,E)=(f_v(V,E))_{v\in V}$, where $f_v(V,E)$ measures the centrality of $v\in 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 \emph{connectivity centrality measure} as the function $c$ on $\cal G$ that assigns to every $(V,E)\in{\cal G}$ the vector of connectivity degrees of its vertices $c(V,E)=(c_v(V,E))_{v\in V}$.
The properties and examples above in fact support this definition.
Indeed, if $\{v,w\}\in E$ is a bridge in $(V,E)\in{\cal 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~\ref{ratio-vertices}.
As shown by Example~\ref{ex:star}, 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~\ref{fig:path} and \ref{fig:degrees} 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.

{\it Single vertex normalization:} \ A centrality measure $f$ on $\cal 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.
\begin{remark}
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.
\end{remark}
{\it The ratio property:} \ A centrality measure $f$ on $\cal G$ satisfies the ratio property if for every $(V,E)\in{\cal 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.

{\it Leaf consistency:} \ A centrality measure $f$ on $\cal G$ satisfies leaf consistency if for every $(V,E)\in\cal 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 ${\cal T}$ the connectivity centrality measure can be characterized by these three axioms.
\begin{theorem}\label{charac}
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.
\end{theorem}
\begin{proof} The proof is by induction on $|V|$.
Let $f$ on ${\cal 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)\in{\cal 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|\geq2$, 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~\ref{cor:non-cut} 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\ne v$.
Since $f_v(V,E)=c_v(V,E)$, Theorem~\ref{ratio-vertices} implies that $f_w(V,E)=c_w(V,E)$ for all $w\neq v$, which completes the proof.
\end{proof}
Note that in the proof the determination of $f_w(V,E)$, $w\in V$, is independent of the choice of the leaf $v$.
The result of Theorem~\ref{charac} is not extendable to a class of connected graphs that also may contain cycles.
For example, each centrality measure on a subclass ${\cal G}'\subseteq \cal G$ satisfying ${\cal G}'\varsupsetneq{\cal T}$, defined on $\cal T$ as the connectivity centrality measure $c$ and on ${\cal G}'\setminus\cal T$ as $\alpha c$ for some real $\alpha\ne 0$, meets all three axioms, since ${\cal G}'\setminus \cal T$ contains only graphs with at least three vertices and $(V_{-v},E_{-v})\in{{\cal G}'\setminus\cal T}$ whenever $(V,E)\in{{\cal G}'\setminus\cal T}$ and $v$ is a leaf in $(V,E)$.
\section{Acknowledgment}
The authors would like to thank Ren\'e van den Brink, Pavel Chebotarev, Dinard van der Laan, M\'{a}nuel M\'{a}g\'{o}, Jacco Thijssen, and two anonymous reviewers for their helpful remarks and suggestions.
The result in Theorem~\ref{zero-theorem} was pointed out to the authors by M\'{a}nuel M\'{a}g\'{o}.
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.

\begin{thebibliography}{9}
\bibitem{borgatti-everett}
S. P. Borgatti and M. G. Everett, A graph-theoretic perspective on centrality, {\it Social Networks} {\bf 28} (2006), 466--484.
\bibitem{dash}
D. Dash, Distributed Resource Allocation with Local Information, Doctoral thesis, Rice University, 2013.
\bibitem{ehrenfest}
P. Ehrenfest and T. Ehrenfest, \"Uber eine Aufgabe aus der Warscheinlichkeitsrechnung die mit der kinetischen Deutung der Entropievermehrung zusammenh\"angt, {\it Mathematisch Naturwissenschaftliche Bl\"atter} {\bf 3} (1906), 128.
\bibitem{fontene}
G. Fonten\'e, G\'en\'eralisation d'une formule connue, {\it Nouv. Ann. Math.} {\bf 15} (1915), 112.
\bibitem{gould}
H. W. Gould, The bracket function and Fonten\'e-Ward generalized binomial coefficients with application to Fibonomial coefficients, {\it Fibonacci Quart.} {\bf 7} (1969), 23--40, 55.
\bibitem{leroy-rigo-stipulanti}
J. Leroy, M. Rigo, and M. Stipulanti, Generalized Pascal triangle for binomial coefficients of words, {\it Adv. in Appl. Math.} {\bf 80} (2016), 24--47.
\bibitem{loeb}
D. E. Loeb, A generalization of the binomial coefficients, {\it Discrete Math.} {\bf 105} (1992), 143--156.
\bibitem{norris}
J. R. Norris, \emph{Markov Chains}, Cambridge University Press, 1997.
\bibitem{sloane}
N. J. A. Sloane et al., On-line Encyclopedia of Integer Sequences, {\url{https://oeis.org}}, 2022.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 05A10; Secondary 05C05, 11B65, 60J10, 91A43.

\noindent \emph{Keywords:}
binomial coefficient, Pascal's triangle, connected graph, Markov chain, centrality measure.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 15 2022;
revised version received  March 31 2023.
Published in {\it Journal of Integer Sequences}, April 8 2023.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}
