2
$\begingroup$

I am using math as a tool and for entertainment, I am not a pro, I do not understand most of the posts here but I am glad such site exists.

Anyway, a friend asked me a question the other day, and I was able to redefine it in terms of a directed graph where all nodes in and out degree equal to 1. I know that If if each node's indegree equals to outdegree that is called an Eulerian graph, what I am asking is a special case of these graphs. Do they have a name or are their properties known?

  • 3
    try to show that such graphs are a collection of circles2010-12-15
  • 1
    @Prometheus: I didn't quite understand what you mean by that. Why should I do that? All I ask is if the properties of a directed graph with indegree = outdegree = 1 are known.2010-12-15
  • 0
    "Why should I do that?" Because the properties of collections of circles are known.2010-12-15
  • 0
    @Prometheus - This only holds for finite graphs, it was not meantioned but probably what the OP wants.2012-07-31

2 Answers 2

5

These types of graphs are equivalent to permutations (or permutations without fixed points, if you're not allowed a vertex to have an edge to itself). If there is an edge from a to b, then a is mapped to b. These are extremely well-studied in mathematics.

[As Prometheus remarks, permutations are equivalent to a collection of cycles]

  • 1
    ?This special case of permutations is is called Derangement: http://en.wikipedia.org/wiki/Derangement2010-12-15
  • 0
    If the number of nodes is finite, then the digraph must be a disjoint union of closed loops (circuits), including self-loops as a special case as Douglas S. Stones notes. However if infinitely many nodes are allowed we could have also some infinite components, where countably many nodes are arranged sequentially like the integers (so not a closed loop).2010-12-15
2

Interestingly the situation you describe, a digraph where all nodes have in and out degree equal to 1, is in essence a simple model of classical mechanics in physics, especially if we allow infinite numbers of vertexes. For a simple discussion of this see the first lecture in Susskind's Theoretical Minimum. The disconnectedness of the graph (i.e. the number of separate cycles) identifies a conserved property. And yes, the name for this type of graph is "permutation".