Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs Original Research Article

We investigate the complexity of several domination problems on the complements of bounded tolerance graphs and the complements of trapezoid graphs. We describe an O(n2 log5 n) time and O(n2) space algorithm to solve the domination problem on the complement of a bounded tolerance graph, given a square embedding of that graph. We also prove that domination, connected domination and total domination are all NP-complete on co-trapezoid graphs.