Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
try to show that such graphs are a collection of circles –  Prometheus Dec 15 '10 at 8:13
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. –  nimcap Dec 15 '10 at 8:46
    
"Why should I do that?" Because the properties of collections of circles are known. –  Qiaochu Yuan Dec 15 '10 at 19:30
    
@Prometheus - This only holds for finite graphs, it was not meantioned but probably what the OP wants. –  Belgi Jul 31 '12 at 10:35

2 Answers 2

up vote 5 down vote accepted

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]

share|improve this answer
1  
?This special case of permutations is is called Derangement: en.wikipedia.org/wiki/Derangement –  nimcap Dec 15 '10 at 12:08
    
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). –  hardmath Dec 15 '10 at 19:21

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".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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