Problème de calcul difficile sur une classe spéciale de graphes bipartis

Je suis intéressé par les propriétés d'une classe de graphes bipartites où tous les nœuds sont 3 réguliers, tous les noeuds sont 2 réguliers, et. Tout d'abord, s'agit-il d'une classe de graphiques bien connue? Deuxièmement,$G(X \cup Y, E)$$X$$Y$$|X|=|2Y/3|$

Existe-t-il un exemple de problème de calcul insoluble limité à cette classe de graphes bipartis?

Etant donné un graphe 3-régulier vous pouvez construire un graphe bipartite avec les propriétés requises en choisissant et et pour chaque arête add arêtes . Je pense donc que vous pouvez trouver des problèmes difficiles à partir de problèmes difficiles sur des graphiques à 3 niveaux.$G = \{V,E\}$$G'$$X = V$$Y = E$$e_k = (u_i,u_j) \in E$$(u_i, e_k), (e_k, u_j)$

Par exemple, l'ISOMORPHISME SOUS-GRAPHIQUE est NP-difficile pour votre classe de graphiques.

La réduction est du cycle hamiltonien sur des graphes à 3 régularités: étant donné un graphe à 3 régularités , construisez le et recherchez un sous-graphe qui est un cycle simple fermé de longueur. a un sous-graphe isomorphe à si et seulement si a un cycle hamiltonien.$G$$G' = \{X \cup Y, E'\}$$H'$$2|V|$$G'$$H'$$G$

Ces graphiques sont les graphiques d'incidence des graphiques cubiques, c'est-à-dire 2 segments de graphiques réguliers. Je vais écrire pour le graphe d'incidence de  .$I(G)$$G$

Étant donné un graphique  et un entier  , il est NP-complet de déterminer si le nombre de croisements de est au plus  (c'est-à-dire, si peut être tracé dans le plan avec au plus  bords se croisant), même si  est restreint à être cubique. De toute évidence, le nombre de croisements n'est pas affecté par l'ajout d'un sommet supplémentaire au milieu de chaque arête. (Source: Hlineny, "Le nombre de croisements est difficile pour les graphiques cubiques", J. Combin. Théorique. B 96 (4): 455–471; DOI .)$G$$k$$G$$k$$G$$k$$G$

Il est possible que le problème de bande passante pour ces graphiques soit NP-complet, car il est NP-complet pour les arbres où chaque sommet a un degré au plus trois. (Source: problème GT40 à Garey et Johnson pour les graphiques généraux; pour les arbres à faible degré, Garey, Graham, Johnson et Knuth, "Complexity results for bandwidth minimisation", SIAM J. Appl. Math. 34: 477-495; Citeseer . )

Divers problèmes de graphes NP-complets restent ainsi sur les graphiques cubiques et ceux-ci conduisent à des problèmes NP-complets sur les graphiques d'incidence correspondants qui sont raisonnablement naturels. Par exemple, demander si un graphe cubique  a un ensemble de taille dominant au plus  équivaut à demander si est une union d'au plus  copies de . De même, un ensemble indépendant dans le graphe cubique correspond à un ensemble de copies disjointes de dans .$G$$k$$I(G)$$k$$I(K_{1,3})$$I(K_{1,3})$$I(G)$