Spektraltechniken für die Gattung eines Graphen

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

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 .$\rho(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)$\rho(G) = \sqrt{8\Delta(G)} + O(\sqrt{g} \log g)$$\Delta(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.

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^\epsilon)$$O(g\sqrt{n})$g $\max\{4g, g+4n\}$$g$$n$

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.