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?


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.