2
$\begingroup$

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

  • 0
    I believe your second condition is called "vertex transitive".2011-11-08
  • 0
    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?2011-11-08
  • 0
    @ccc No, for n=3, hexagonal grid, what else? Also http://en.wikipedia.org/wiki/File:Tiling_Semiregular_4-8-8_Truncated_Square.svg2011-11-08
  • 0
    Also http://en.wikipedia.org/wiki/File:Tiling_Semiregular_3-12-12_Truncated_Hexagonal.svg ok I am convinced http://en.wikipedia.org/wiki/File:Tiling_Semiregular_4-6-12_Great_Rhombitrihexagonal.svg2011-11-08
  • 0
    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.2011-11-08
  • 0
    @ccc, if you could sketch how that gives uncountably many examples, that would be worth an answer, I think.2011-11-08
  • 0
    Just 1 question, if we consider the the sequence: infinite path (n=2), square-grid (n=4), cubic grid (n=6), etc, is there a most natural n=3 and n=5 candidate? Ie n=3 must be a subgraph of the cubic graph, and must contain the square graph, is this possible?2011-11-08
  • 0
    @harry, also regular $n$-gons meeting in threes in the hyperbolic plane (for $n>6$), giving a countably infinite family of examples.2011-11-08
  • 0
    ... or in general, hyperbolic tessellations of $k$-gons ($k>6$, say) meeting in $n$s for a countably infinite familiy of vertex-transitive $n$-regular graphs for each $n\ge 3$.2011-11-08

0 Answers 0