1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.