In der Graphentheorie ist ein Pisot-Graph ein selbstähnlicher Graph, der mit Hilfe einer Pisot-Zahl definiert wird.
Definition Gegeben sei eine Pisot-Zahl . Auf dem Folgenraum wird eine Äquivalenzrelation mittels
definiert.
Die Eckenmenge des Pisot-Graphen ist durch gegeben, wobei die Äquivalenzklassen der Relation bezeichnet. Es gibt also maximal Ecken in , durch die Identifizierungen können es aber auch weniger Ecken sein.
Die Ecke wird mit und durch eine Kante verbunden, hierdurch ist die Kantenmenge gegeben.
Beispiele miniatur|Fibonacci-Graph Der einfachste Pisot-Graph ist der Fibonacci-Graph, er ist durch den goldenen Schnitt bestimmt, der die Gleichung erfüllt. Aus dieser Gleichung ergibt sich, dass mit identifiziert wird, weshalb in diesem Fall nur 7 Ecken hat.
Ähnlich wird (1,0,0,0) mit (0,1,1,0), (1,0,0,1) mit (0,1,1,1), (0,1,0,0) mit (0,0,1,1) und (1,1,0,0) mit (1,0,1,1) identifiziert, weshalb in diesem Fall nur 12 Ecken hat.
Der Fibonacci-Graph kann auch als Cayley-Graph der Halbgruppe beschrieben werden.
Weitere Pisot-Graphen erhält man durch andere Pisot-Zahlen. Insbesondere ist der durch die Nullstelle von bestimmte Graph nicht planar, siehe Abbildung. miniatur|Ein nicht planarer Pisot-Graph
Wachstumsrate Die Wachstumsrate des Pisot-Graphen ist durch gegeben. Dies ist eine Konsequenz des klassischen Garsia-Lemmas.A.M. Garsia: Arithmetic properties of Bernoulli convolutions, Trans. Amer. Math. Soc. 162, 409–432, 1962, .
Literatur J. Neunhäuserer: Random walks on infinite self-similar graphs. In: Electronic Journal of Probability, Band 12 (2007), Artikel 46, S. 1258–1275, .
Weblinks Salem Numbers, Pisot Numbers, MahlerMeasure, and Graphs (PDF-Datei; 854 kB) J. Neunhäuserer: Random walks on infinite self-similar graphs.
Einzelnachweise
Kategorie:Graphenklasse