Yet another graph characteristic

Question

I wonder if the following graph-theoretical concepts have been considered before, and if so, under which name.

---

Consider a directed graph $G$ with $n$ nodes.

Let the cycle number $\gamma(\nu)$ be the length of the shortest directed cycle from node $\nu$ to itself. $\gamma(\nu) = 1$ when $\nu$ is connected to itself. Let $\gamma(\nu) = 0$ when there is no cycle from $\nu$ to itself.

Let the mean cycle number $\overline{\gamma}(G)$ be $\frac{1}{n}\sum_{i=1}^n \gamma(\nu_i)$.

Let the shortcutness $\sigma(e)$ of edge $e$ be the number

$$\sigma(e) = 1 - \frac{\overline{\gamma}(G\setminus\{e\})}{\overline{\gamma}(G)}$$

When $\sigma(e)=0$, i.e. $\overline{\gamma}(G\setminus\{e\}) = \overline{\gamma}(G)$, then edge $e$ doesn't act as a shortcut.

When $\sigma(e)=1$, i.e. $\overline{\gamma}(G\setminus\{e\}) = 0$, then edge $e$ is contained in every cycle and thus is an ubiquitous shortcut.

Let the cycle number spectrum be the function $f: \{0,\dots,n\} \rightarrow \{0,\dots,n\}$ with $f(k)$ being the number of nodes $\nu$ with $\gamma(\nu) = k$. We have $\sum_{k=0}^n f(k) = n$.

---

My questions are:

Have some of these concepts be found useful in graph theory? If so, under which names?

How can they be related to other graph characteristics?

Which functions $f: \{0,\dots,n\} \rightarrow \{0,\dots,n\}$ with $\sum_{k=0}^n f(k) = n$ can not be cycle number spectra of any graph?

Answer 1

The "cycle number of a graph" is (roughly) equivalent to (the output of) Dijkstra's algorithm in the following sense

If you fix $i\in V$ and run Dijkstra's algorithm for the pairs $(i,j)$ and $(j,i)$ for $j \in V$ and let $D_{i,j}= $"the output on $i,j$" then \begin{equation} \gamma(i)= \min_{j \in V}\{D_{i,j}+D_{j,i}\}. \end{equation}

This can be further simplified by limiting the search to the 2-connected components found using the algorithm by Hopcroft and Tarjan.

Chapter 3 of Diestel's Graph Theory is dedicated to the subject of connectivity and in the notes for that chapter (at the end of the chapter) he states:

Although connectivity theorems are doubtless amongst the most natural, and also the most applicable, in graph theory, there is still no comprehensive monograph on this subject.

However right after that sentence he gives a large bibliography of books and papers where you can find more results.

If you want to consider graphs with (arbitrary) edge weights then this is a topic of intense study in computer science, so maybe the short and simple book by Even might be useful in this case (however computer scientists usually consider network flows which may or may not be useful for obvious reasons).

If we are setting all edges to 1 then, in this case, it may be useful to consider the cycle space which is defined as a subspace of the vector space of edges, let's call it $\mathcal{E}$, over $\mathbb{F}_2$ (or $\mathbb{Q}$ or module over $\mathbb{Z}$) of formal sums of the form $\sum_{e \in E} c_e e $ for $c_e \in \mathbb{F}_2$ (or $\mathbb{Q}$ or $\mathbb{Z}$ or $\mathbb{R}$ etc ...). In this case, we have that the Euler characteristic of an equation that a graph must satisfy; i.e. \begin{equation}\chi(G) = |V|-|E|+|F| = \textrm{rank}(\mathcal{V}) - \textrm{rank}(\mathcal{E} ) + \textrm{rank}(\mathcal{F} ) \end{equation} but actually, if you analyze the algebraic topological proof of the formula you actually have a chain complex of linear maps \begin{equation} \mathcal{F} \overset{d_1}{\longrightarrow} \mathcal{E} \overset{d_0}{\longrightarrow} \mathcal{V} \end{equation} so that the cycle space is $\textrm{ker}(d_0)$; which converts this into a statement about cycles see relation between the fundamental group and first homology group. See chapter 6 of Singer and Thorpe for an elementary treatment or Hatcher for a more in-depth explanation.

Finally The answer to your last question:

Which functions $f:\{0,...,n\}\rightarrow\{0,...,n\}$ with $\sum^n_{k=0}f(𝑘)=n$ can not be cycle number spectra of any graph?

Well this is only an interesting problem for edge weights equal to one. So let us assume this. Here is one interesting constraint

Claim If $i$ has a minimal cycle of size $k$ for some $i$ then $|f^{-1}(\{1,...,k\})|\geq k-1 $. In other words \begin{equation} f(k)>0 \implies |f^{-1}(\{1,...,k\})|\geq k-1 \end{equation}

(Proof): If some $i$ has a minimal cycle $i=c_1...c_{k+1}=i$ then each of the $c_j$ for ($j \neq 1,k+1$) has a minimal cycle of size lower than $k$. QED

Phrased in the language of impossibility we have

If $|f^{-1}(\{1,...,k\})| < k-1$ then $f(k) $ cannot be positive.