ISGCI project home All classes SmallgraphsGraphclass: weak dominating pair
Definition:
A pair of vertices in a graph is called a dominating pair if the vertex set of every path between these two vertices is a dominating set.
A graph is a weak dominating pair
graph if it has a dominating pair.
References:
[1211]
Related classes:
dominating pair
Inclusions
Maximal subclasses:
AT-free 
claw-free (Cn+6,X37,claw,co-antenna,net,sun)-free PI* alternately orientable co-comparability bounded tolerance dominating pair intersection graphs of parallelograms (squares)
Problems summary
| Recognition: |
Unknown to ISGCI
| details |
| Cliquewidth expression: |
Unbounded or NP-complete
| details |
| Cliquewidth: | Unbounded | details |
| Weighted independent set: |
Unknown to ISGCI
| details |
| Independent set: |
Unknown to ISGCI
| details |
| Domination: |
Unknown to ISGCI
| details |
Algorithms for Recognition
Algorithms for Cliquewidth expression
See also
: Cliquewidth : Weighted independent set : Domination
Algorithms for Cliquewidth
Unbounded from bipartite permutation
[1182]
Unbounded from (2K2,co-(C6),odd anti-cycle)-free
Unbounded from (C5,P,P5,co-(P),bull,co-gem,fork)-free
[1185]
Unbounded from co-comparability graphs of posets of interval dimension 2, height 1
Unbounded from permutation
[1177]
Unbounded from (3K1,co-(H))-free
Unbounded from unit interval
[1177]
Unbounded from (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(X85))-free
Unbounded from (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(K1,4),co-(X85))-free
Unbounded from co-bipartite
Unbounded from (3K1,co-cross)-free
Unbounded from (2K3,3K1,co-(A),co-(H),co-(X45))-free
Unbounded from (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free
See also
: Cliquewidth expression Algorithms for Weighted independent set
See also
: Cliquewidth expression : Independent set
Algorithms for Independent set
See also
: Weighted independent set
Algorithms for Domination
See also
: Cliquewidth expression