Låt G = (V, E) vara en ansluten oriktad graf. För alla vertex v V, den stängda grannen- En uppsättning S är en svagt ansluten dominerande uppsättning av G om S dominerar och S w är ansluten. Det svagt sammankopplade dominansnumret är γ w (G) = min{  och S är en svagt sammankopplad dominerande uppsättning av G }, och det övre svagt sammankopplade dominansnumret är ρ w (G) = max{  och S är en minimal svagt sammankopplad dominerande uppsättning av G }. Det svagt sammankopplade oberoende dominansnumret, i w (G) = min{  och S är en svagt sammankopplad oberoende dominerande uppsättning av G }, och det övre svagt sammankopplade oberoende dominanstalet, β w (G) = max {  och S på grund av att S är en svagt sammankopplad oberoende dominerande uppsättning av G }, existerar alltid. Vi visar att problemen med beräkning γ w, i w, β w, och ρ w är NP-hård; visa att det finns linjära algoritmer för att beräkna γ w (T ) och ρ w (T ) för ett träd T och i w (G) och β w (G) för en ansluten bipartit graf G; och ge skarpa nedre och övre gränser på γ w (G) för en ansluten graf G.
Problemet med att hitta en WCDS med minimal kardinalitet är NP-hård REF.
On Weakly-connected Domination in Graphs
{'venue': 'Discret. Math.', 'journal': 'Discret. Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}