Skip to main content
Notice removed Authoritative reference needed by CommunityBot
Bounty Ended with Pedro Juan Soto's answer chosen by CommunityBot
Notice added Authoritative reference needed by Hans-Peter Stricker
Bounty Started worth 100 reputation by Hans-Peter Stricker
added 8 characters in body
Source Link
Hans-Peter Stricker
  • 9.7k
  • 5
  • 53
  • 113

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?

Can the cycle number spectrumHow 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?

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?

Can the cycle number spectrum be related to other graph characteristics?

Which functions $f: \{0,\dots,n\} \rightarrow \{0,\dots,n\}$ can not be cycle number spectra of any graph?

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?

Source Link
Hans-Peter Stricker
  • 9.7k
  • 5
  • 53
  • 113

Yet another graph characteristic

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?

Can the cycle number spectrum be related to other graph characteristics?

Which functions $f: \{0,\dots,n\} \rightarrow \{0,\dots,n\}$ can not be cycle number spectra of any graph?