0
$\begingroup$

The definition of girth of an undirected graph is defined as the length of the smallest cycle in the graph. Some directed graphs have no cycle (a directed path that stars and ends at the same vertex) but has two different directed paths between two vertices $v$ and $w$, say both paths go from $v$ to $w$. For a Cayley hash function that corresponds to a collision so it is desirable that the Cayley graph associated to the hash function to have large girth. How one can define the girth in a directed graph?

$\endgroup$
1
$\begingroup$

The girth for directed graphs is usually defined as the directed girth, that is, the minimum length of a directed cycle (or $\infty$ if no directed cycles exist). For instance, see

  • Jørgen Bang-Jensen and Gregory Gutin, Digraphs: Theory, Algorithms and Applications (Second Edition), Springer Monographs in Mathematics. (The definition is given in chapter 1. Further properties of the girth are examined in section 8.4.)

For your purpose, the girth of a directed graph is not a very useful concept, as you are not interested in directed cycles but rather in vertex-disjoint paths with the same start and end vertices. You could consider the undirected girth of the graph (that is, the girth of the underlying undirected graph). I'm not entirely sure, but I think this doesn't show the exact information you want to see: the directed cycles are also included in this figure. Indeed it could happen that a graph has a small directed cycle but only very large vertex-disjoint paths with the same start and end vertices (or no such paths at all).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.