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?
> 
> 
> 



Yet another graph characteristic
The "cycle number of a graph" is (roughly) equivalent to (the output of) [Dijkstra's algorithm](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Biconnected_component) found using the algorithm by [Hopcroft and Tarjan](https://dl.acm.org/doi/10.1145/362248.362272). 


Chapter 3 of [Diestel's Graph Theory](http://diestel-graph-theory.com/) 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](https://g.co/kgs/wtrX4L) might be useful in this case (however computer scientists usually consider [network flows](https://en.wikipedia.org/wiki/Flow_network) 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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*](https://en.wikipedia.org/wiki/Fundamental_group#Relationship_to_first_homology_group). See chapter 6 of [Singer and Thorpe](https://g.co/kgs/JHWUHs) for an elementary treatment or [Hatcher](https://g.co/kgs/VPH5Pq) 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.**
> 
> 
> 


