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.

How many infinite connected graphs are there, that satisfy:
-Every node has $n$ neighbours
-Every node is symmetric, ie take two graphs and any one point on each, then we can strecth one graph to have the two points ontop of eachother, aswell as having all other nodes and vertices coincide (is there a name for this?)

For instance for n=2, only an infinite line with countably infinite nodes on it is possible

share|improve this question
    
I believe your second condition is called "vertex transitive". –  Austin Mohr Nov 8 '11 at 4:12
    
If Austin is correct and you mean "vertex transitive," then there are certainly infinitely many nonisomorphic graphs already at $n=3$. Did you mean something else? –  user83827 Nov 8 '11 at 4:21
    
@ccc No, for n=3, hexagonal grid, what else? Also en.wikipedia.org/wiki/… –  harry_b Nov 8 '11 at 4:28
    
Also en.wikipedia.org/wiki/… ok I am convinced en.wikipedia.org/wiki/… –  harry_b Nov 8 '11 at 4:35
    
There are literally too many examples to list (there are uncountably many examples for each $n \geq 3$). The way I'm thinking about it is by fiddling with Cayley graphs of groups, but if you just care about getting an infinite collection there are probably simpler techniques. –  user83827 Nov 8 '11 at 4:35

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.