3
$\begingroup$

Are infinite cycle graphs just "straight lines"?

I mean are they of the form: $\cdots \bullet - \bullet - \bullet - \bullet - \bullet - \cdots $

  • 0
    It is hard to say if $\mathbb Z \cup \infty$ is an infinite cycle graph-which elements does $\infty$ connect to? What is your definition of a cycle graph? Given the definition, the answer might be available.2012-12-25

2 Answers 2

9

Yes (that is, if one decided that "infinite cycle graph" ought to be meaningful, it ought to mean this to be consistent with the meaning of "infinite cyclic group"). More generally, see Cayley graph.

4

A discussion of what could constitute a sensible definition of an "infinite cycle" was given in:

R. Diestel, On Infinite Cycles in Graphs---or How to Make Graph Homology Interesting, American Mathematical Monthly, 111 (2004), 559-571.

I won't go into too much detail here, but here's a sketch of some of the ideas:

  • He dismisses the "infinite path = infinite cycle" definition, writing common sense tells us that this can hardly be right (and points out how important results for finite cycles break down if we allow infinite cycles under this definition).

  • He discusses compactification of the infinite path, where there is a "point at infinity" (analogous to how the real number line with a point at infinity and the circle are homeomorphic). However, he points out that cycles could have more than one "point at infinity", and, in fact, an infinite number of "points at infinity", which also results in problems.

  • He suggests a topological solution to the problem:

Put a topology on the graph and its ends, and define a "cycle" (finite or infinite) simply as a circle in this space, a homeomorphic image of the unit circle in the complex plane.


Infinite analogues of results concerning cycles in graph theory were also given in:

R. Diestel, D. Kühn, On infinite cycles. I, Combinatorica 24 (2004), 69-89.

and

R. Diestel, D. Kühn, On infinite cycles. II, Combinatorica 24 (2004), 91–116.