Is there a classification for a graph with the following properties?

  1. Finite.
  2. Directed.
  3. Every vertex points to some vertex.

The third property necessitates the existence of at least one cycle. All "paths" must eventually lead to a cycle.

I've looked through a glossary of graph theory but haven't found any terms that describe the above.

I can say that the above "is neither injective nor surjective," but I was hoping for a more positively descriptive name.

  • $\begingroup$ @NoahSchweber - Thanks, fixed. I didn't consider infinite graphs. $\endgroup$ – Andrew Cheong May 16 '16 at 3:53
  • 1
    $\begingroup$ Do you need a one-word answer? I'd just call it a sinkless finite digraph. (Reminds me of the old riddle, "What has one eye, one horn, flies, and eats people? A one-eyed, one-horned, flying people-eater.") $\endgroup$ – bof May 16 '16 at 4:26
  • $\begingroup$ @bof - Nope, I just needed a consistent term to use, and saying "Finite and directed where every vertex points to some vertex," was too much. Your "sinkless" is perfect, I think. Sinklessness implies that every vertex points somewhere (so edgeless vertices are disqualified). Would you like to add it as an answer? Because it's what I'll be using. $\endgroup$ – Andrew Cheong May 16 '16 at 4:30

I'd just call it a sinkless (finite) digraph.


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.