Almost well-dominated bipartite graphs with minimum degree at least two

Abstract

A dominating set in a graph G = (V, E) is a set S such that every vertex of G is either in S or adjacent to a vertex in S. While the minimum cardinality of a dominating set in G is called the domination number of G denoted by Gamma(G), the maximum cardinality of a minimal dominating set in G is called the upper domination number of G denoted by Gamma(G). We call the difference between these two parameters the domination gap of G and denote it by mu(d)(G) = Gamma(G) - Gamma(G). While a graph G with mu(d)(G) = 0 is said to be a well-dominated graph, we call a graph G with mu(d)(G) = 1 an almost well-dominated graph. In this work, we first establish an upper bound for the cardinality of bipartite graphs with mu(d)(G) = k, where k >= 1, and minimum degree at least two. We then provide a complete structural characterization of almost well-dominated bipartite graphs with minimum degree at least two. While the results by Finbow et al. [Ars Comb. 25A (1988) 5-10] imply that a 4-cycle is the only well-dominated bipartite graph with minimum degree at least two, we prove in this paper that there exist precisely 31 almost well-dominated bipartite graphs with minimum degree at least two.