scientific article; zbMATH DE number 108143

Publication date 23 January 1993

conformal length of graphs lower bound minimal cut Möbius function torus tree upper bound

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35)

Review text

In dieser Arbeit soll die Konformlänge von Graphen untersucht werden. Der Begriff der Konformlänge eines Graphen entsteht durch Übertragung des von \textit{P. Li} und \textit{S.-T. Yau} [Invent. Math. 69, 269-291 (1982; Zbl 0503.53042)] eingeführten Konzeptes des Konformvolumens einer kompakten Riemannschen Mannigfaltigkeit auf Graphen. Zur Definition der Konformlänge eines Graphen \(G\) betrachten wir Realisierungen des Graphen in der \((k-1)\)-dimensionalen Einheitssphäre \(S^{k-1}\subseteq\mathbb{R}^ k\), d.h. injektive Abbildungen \(f\) von der Eckenmenge \(W\) nach \(S^{k-1}\). Die Kanten des Graphen werden dabei auf die kürzeste Verbindung zwischen den Bildern der Ecken auf \(S^{k-1}\) abgebildet. Dabei sind Überschneidungen von Kanten zugelassen. Dann definieren wir die Konformlänge eines Graphen \(\text{kVol}(G)\), als das Infimum der unter Möbiusabbildungen invarianten Funktion \[ \sup_{g\in M}L_ G(g\circ f)=\sup_{g\in M}\sum_{\{w_ i,w_ j\}\in X}\arccos\langle g\circ f(w_ i),g\circ f(w_ j)\rangle, \] also \[ \text{kVol}(G)=\inf_{f\in R}\sup_{g\in M}L_ G(g\circ f). \] Hierbei bezeichne \(M\) die Menge der Möbiusabbildungen und \(R\) die Menge der \((k-1)\)-dimensionalen Realisierungen. Anschaulich beschreibt die Konformlänge so etwas wie die minimale konforme Länge eines Graphen, d.h. die durch Möbiusabbildungen auf der Sphäre \(S^{k-1}\) nicht weiter vergrößert werden kann. Da es für gegebene Graphen ein schwieriges Problem ist, die Konformlänge exakt zu bestimmen, ist man daran interessiert, gute untere und obere Schranken für das Konform-Volumen anzugeben. Wir werden in dieser Arbeit untere (Kapitel 1) und obere Schranken (Kapitel 3) angeben, die sich für viele Familien von Graphen höchstens um einen konstanten Faktor unterscheiden (Kapitel 5, Beispiel Torusgraphen und \(K_ n)\). Im einzelnen werden wir in Satz 1, Kapital 1 eine untere Schranke angeben, welche nur von der Anzahl der Kanten zwischen den minimalen Schnitten des Graphen, der Anzahl der Ecken von \(G\) und der Anzahl der Ecken des minimalen Schnittes abhängt. Dabei versteht man unter einem minimalen Schnitt eine Zerlegung der Eckenmenge \(W\) in zwei Teilmengen \(W_ 1\) und \(W_ 2\) derart, daß bei gegebener Mächtigkeit von \(W_ 1\) und \(W_ 2\) die Anzahl der Kanten zwischen \(W_ 1\) und \(W_ 2\) minimal wird. Solche minimalen Schnittzahlen sind aus graphentheoretischen Anwendungen bekannt, und an Algorithmen zur Berechnung wird im Zusammenhang mit dem Entwurf von integrierten Schaltkreisen gearbeitet. In der Proposition verbessern wir die untere Schranke von Satz 1, indem wir Zerlegungen in vier Teilmengen betrachten. Mit Hilfe dieses Ergebnisses geben wir in Satz 2 eine weitere untere Schranke für die Konformlänge an, bei der jedoch nur Zerlegungen zugelassen sind, bei denen das Verhältnis der Anzahlen der Ecken in beiden Teilen einen gewissen Wert \({1\over 2k-1}\) nicht unterschreitet. Es zeigt sich, daß für viele Graphen die Schranke von Satz 2 besser ist, als die in Satz 1 (für den vollständigen Graphen \(K_ n\) ist sie sogar von besserer Größenordnung, siehe Kapitel 4). Eine Verallgemeinerung der Sätze 1 und 2 für Graphen mit Ecken und Kantengewichten wird in Kapitel 2 bewiesen. In Kapitel 3 wird durch Wahl einer speziellen Realisierung \(g\) eine obere Schranke hergeleitet. Für ein Gitter auf einem Torus werden wir dann in Kapitel 4 zeigen, daß sich die beiden Schranken im wesentlichen nur um einen Faktor \(\pi/2\) unterscheiden. Schließlich werden wir in Kapitel 5 für die Klasse der Bäume die Konformlänge exakt berechnen und beweisen, daß sie gleich der maximalen Valenz mal \(\pi\) ist.

Recommendations

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4023716)