DI-Pathological Graphs & Inverse Dominating Sets
Please note that the following files are PDF files; therefore, you will need the free adobe acrobat reader in order to be able to view these files. If you do not have this application, you can download it for free here. If you’re not sure, try it out, and see if it works.
A DI-pathological graph is a graph in which every minimum dominating set intersects every maximal independent set. DI-patholigcal graphs are related to the Inverse Domination Conjecture; hence, it is useful to characterize properties of them. One characterization question is how large or small a graph can be relative to the domination number. Two useful characterizations of size seem relevant, namely the number of vertices and the number of edges. In this talk, we provide two results related to this question. In terms of the number of vertices, we show that every connected, DI-pathological graph with no isolated vertices has at least $2\gamma(G)+4$ vertices except the complete bipartite graph with three vertices in each partition, the complete bipartite graph with three vertices in one partition and four vertices on the other, and five graphs on nine vertices and show that our lower bound is best possible. We then show that with one exception, every connected, DI-pathological graph with no isolated vertices has at least $2\gamma(G)+5$ edges and show that our lower bound is best possible.