Spektraltechniken für die Gattung eines Graphen

8

Eine allgemeine Frage: Gibt es spektrale Techniken, um die Gattung eines Graphen abzuschätzen? Ich interessiere mich für zweigeteilte Graphen.

T ....
quelle
Könnten Sie bitte Hintergrundinformationen liefern?
Mohammad Al-Turkistany
Ich denke, es ist eine allgemeine Frage. Wie viele Ziehpunkte benötigen wir, um ein Diagramm nicht überschneidend einzubetten? Neugierig, ob Laplace-Techniken dies studieren können?
T ....
Danke Arul, kannst du es deiner Frage hinzufügen?
Mohammad Al-Turkistany
Vielleicht interessiert Sie ein verwandter Beitrag auf MO: mathoverflow.net/questions/54395/… .
Hsien-Chih Chang 5 之

Antworten:

6

Es mag schwierig sein, die genaue Grenze für die Gattung eines Graphen mittels Spektraltechniken zu bestimmen, aber es scheint möglich, eine Ober- oder Untergrenze anzugeben. Die folgende Arbeit gibt eine Möglichkeit, die Gattung anhand des größten Eigenwerts der Adjazenzmatrix, dh des Spektralradius , abzuschätzen .ρ(G)

Spektraler Radius von endlichen und unendlichen planaren Graphen und von Graphen der begrenzten Gattung , Zdenek Dvorak und Bojan Mohar, JCTB 2010.

Sie bieten einen oberen auf der spektralen Radius für eine Gattung gebunden Graph, wie in der folgenden Satz angegeben.g

Satz. Für eine Genus Graph, , wobei den maximalen Grad des Graphen bezeichnet .ρ ( G ) = gΔ(G)G.ρ(G)=8Δ(G)+O(glogg)Δ(G)G

Wir können dies verwenden, um eine Untergrenze für die Gattung eines Graphen zu schätzen, wenn der spektrale Radius des Graphen groß genug ist. Eine genauere Bindung für die Big-O-Konstante finden Sie im Papier.

Die Eigenschaft als zweiteiliger Graph scheint hier wenig zu helfen. Sie sind in der Lage, eine zweiteilige Instanz bereitzustellen, in der die Ungleichung in planaren Graphen am besten möglich ist.

Hsien-Chih Chang 張顯 之
quelle
Tatsächlich ist der Fehlerterm in der Formel interessant - hat einen ähnlichen Ausdruck wie der Fehlerterm aus der Anzahl der Primzahlen, die unter einer bestimmten Zahl unter der GRH liegen.
T ....
Aber es gibt keine Schätzung für die Gattung. Es liefert eine Schätzung für den Spektralradius.
T ....
1
Wir müssen es rückwärts verwenden. Wenn der Spektralradius groß genug ist, wissen wir, dass die Gattung groß sein sollte. Wenn Sie nach Obergrenzen für die Gattung fragen, sollten Sie dies in der Frage angeben.
Hsien-Chih Chang 18 之
Ich dachte, die Frage sei klar "... schätze die Gattung ..."
T ....
1
Aber ich dachte, der Spektralradius ist der größte Eigenwert der Adjazenzmatrix, der leicht zu berechnen ist. Alles in allem klingt dies nach einer ziemlich anständigen Antwort.
Suresh Venkat
8

Es ist NP-schwer, die Gattung eines Graphen auf einen additiven Fehler von zu approximieren . Es gibt Polynom-Zeit-Algorithmen, die eine Einbettung der Gattung oder berechnen , wobei die wahre Gattung und die Anzahl der Eckpunkte ist. Ein signifikant besserer spektraler oder sonstiger Approximationsalgorithmus wäre ein bedeutender Durchbruch!O ( g O(nϵ)O(gn)g nmax{4g,g+4n}gn

Siehe: Jianer Chen, Saroja P. Kanchi und Arkady Kanevsky. Ein Hinweis zur Annäherung an die Gattung der Graphen . Information Processing Letters 61 (6): 317–322, 1997.

Jeffε
quelle
Gilt das auch für zweigeteilte Graphen?
T ....
6
Das Härteergebnis muss für zweigeteilte Graphen zutreffen, da jeder Graph zweigeteilt werden kann, indem an jeder Kante ein neuer Scheitelpunkt eingeführt wird. Es ist wirklich unwahrscheinlich, dass eine Zweiteiligkeit beim Algorithmus helfen würde.
Jeffs