ISGCI project home All classes SmallgraphsGraphclass: dominating pair
Definition:
A graph is a
dominating pair graph
iff every connected induced subgraph is a
weak dominating pair graph.
References:
[1211]
Related classes:
AT-free chordal 
dominating pair diametral path frame hereditary dominating pair weak dominating pair
Inclusions
Minimal superclasses:
diametral path weak dominating pair
Maximal subclasses:
AT-free (Cn+4,T2,XF2n+1)-free (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,X37,X38,X39,X40,X41,XF2n+1,XF3n,XF4n)-free chordal dominating pair frame hereditary dominating pair
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