Schweres Rechenproblem bei einer speziellen Klasse von zweiteiligen Graphen

Ich interessiere mich für die Eigenschaften einer Klasse von zweigeteilten Graphen denen alle Knoten in X 3-regulär sind, alle Knoten in Y 2-regulär sind und | X | = | 2 Y / 3 | . Erstens: Ist dies eine bekannte Klasse von Graphen? Zweitens,$G(X \cup Y, E)$$X$$Y$$|X|=|2Y/3|$

Gibt es ein Beispiel für ein hartnäckiges Rechenproblem, das auf diese Klasse von zweiteiligen Graphen beschränkt ist?

Bei einem 3-regulären Graphen Sie einen zweigeteilten Graphen G ' mit den erforderlichen Eigenschaften erstellen, indem Sie X = V und Y = E auswählen und für jede Kante e k = ( u i , u j ) ∈ E addieren Kanten ( u i , e k ) , ( e k , u j$G = \{V,E\}$$G'$$X = V$$Y = E$$e_k = (u_i,u_j) \in E$$(u_i, e_k), (e_k, u_j)$. Ich denke also, dass Sie einige schwierige Probleme finden können, beginnend mit schwierigen Problemen in 3-regulären Diagrammen.

Zum Beispiel ist SUBGRAPH ISOMORPHISM für Ihre Klasse von Graphen NP-schwer.

Die Reduktion stammt aus dem Hamilton-Zyklus in 3-regulären Graphen: Wenn ein 3-regulärer Graph , bauen Sie das entsprechende G ' = { X ∪ Y , E ' } und suchen Sie nach einem Teilgraphen H ', der ein geschlossener einfacher Zyklus der Länge 2 ist | V | . G ' hat genau dann einen zu H ' isomorphen Teilgraphen, wenn G einen Hamilton-Zyklus hat.$G$$G' = \{X \cup Y, E'\}$$H'$$2|V|$$G'$$H'$$G$

Diese Diagramme sind die Inzidenzdiagramme von kubischen Diagrammen, auch bekannt als 2 Strecken von 3 regulären Diagrammen. Ich schreibe für das Auftreten Graph von  G .$I(G)$$G$

Bei einem gegebenen Graphen  und eine ganze Zahl  k , ist es NP-vollständig zu bestimmen , ob G ‚s Kreuzungszahl höchstens  k (dh, ob G kann mit höchstens in der Ebene gezogen werden  k Kanten einander kreuzen), auch wenn G  ist beschränkt auf kubisch zu sein. Es ist klar, dass die Kreuzungsnummer nicht durch Hinzufügen eines zusätzlichen Scheitelpunkts in der Mitte jeder Kante beeinflusst wird. (Quelle: Hlineny, "Kreuzungszahl ist schwer für kubische Graphen", J. Combin. Theor. B 96 (4): 455–471; DOI .)$G$$k$$G$$k$$G$$k$$G$

Es ist möglich, dass das Bandbreitenproblem für diese Diagramme NP-vollständig ist, da es NP-vollständig für Bäume ist, bei denen jeder Scheitelpunkt höchstens drei Grade hat. (Quelle: Problem GT40 in Garey und Johnson für allgemeine Diagramme; für Bäume mit niedrigem Grad Garey, Graham, Johnson und Knuth, "Komplexitätsergebnisse für die Bandbreitenminimierung", SIAM J. Appl. Math. 34: 477-495; Citeseer . )

$G$$k$$I(G)$$k$$I(K_{1,3})$$I(K_{1,3})$$I(G)$