Feiner Graph

Ein Graph ${\displaystyle K=(V,E)}$ heißt fein, wenn er eine (und damit jede) der folgenden äquivalenten Bedingungen erfüllt:

• Für jede Kante ${\displaystyle e\in E}$ und jedes ${\displaystyle n\in \mathbb {N} }$ gibt es nur endlich viele durch ${\displaystyle e}$ verlaufende Kreise der Länge ${\displaystyle n}$.
• Für alle Knoten ${\displaystyle x,y\in V}$ und jedes ${\displaystyle n\in \mathbb {N} }$ gibt es nur endlich viele ${\displaystyle x}$ und ${\displaystyle y}$ verbindende Wege ohne sich wiederholende Knoten.
• Für alle ${\displaystyle x,y\in V,n\in \mathbb {N} }$ gibt es keine unendliche Menge ${\displaystyle x}$ und ${\displaystyle y}$ verbindender paarweise unabhängiger Wege ohne sich wiederholende Knoten der Länge ${\displaystyle n}$. (Hierbei heißen zwei Wege unabhängig, wenn sie nur Anfangs- und Endpunkt gemeinsam haben.)
• Wenn ${\displaystyle x,y\in V}$ ein Paar unterschiedlicher Knoten und ${\displaystyle n\in \mathbb {N} }$ ist und ${\displaystyle {\mathcal {L}}}$ eine kanten-endliche Menge zusammenhängender Teilgraphen von ${\displaystyle K}$, die alle jeweils ${\displaystyle n}$ Knoten haben und ${\displaystyle x}$ und ${\displaystyle y}$ enthalten, dann muss ${\displaystyle {\mathcal {L}}}$ endlich sein. (Hierbei heißt eine Menge ${\displaystyle {\mathcal {L}}}$ kantenendlich, wenn jede Kante ${\displaystyle e\in E}$ nur in endlich vielen Teilgraphen aus ${\displaystyle {\mathcal {L}}}$ enthalten ist.)
• Für jeden Knoten ${\displaystyle x\in V}$ ist die Nachbarschaft ${\displaystyle N_{K}(x)}$ lokal endlich in ${\displaystyle K-\left\{x\right\}}$. (Das heißt, jeder Knoten in ${\displaystyle N_{K}(x)}$ ist in ${\displaystyle K-\left\{x\right\}}$ nur zu endlich vielen Knoten aus ${\displaystyle N_{K}(x)}$ adjazent.)

• Lokal endliche Graphen sind fein.
• Der Farey-Graph ist fein.

• Brian Bowditch: Relatively hyperbolic groups. In: Internat. J. Algebra Comput. 22. Jahrgang, Nr. 3, 2012, doi:10.1142/S0218196712500166 (soton.ac.uk [PDF])., Abschnitt 2