Some Bounds on the Size of $DI$-Pathological Graphs

Abstract

A DI-pathological graph is a graph in which every minimum dominating set intersects every maximal independent set. DI-pathological 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 paper, we provide two results related to this question. In terms of the number of vertices, we show that every connected, DI-pathological graph has at least $2\gamma (G)+4$ vertices except $K_{3,3}$, $K_{3,4}$, and six 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.