Almost well-dominated bipartite graphs with minimum degree at least two
Hadi Alizadeh, Didem Gözüpek · RAIRO - Operations Research · 2020
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 Γ(G), the maximum cardinality of a minimal dominating set in G is called the upper domination number of G denoted by Γ(G). We call the difference between these two parameters the domination gap of G and denote it by µd(G) = Γ(G) − Γ(G). While a graph G with µd(G) = 0 is said to be a well-dominated graph, we call a graph G with µd(G) = 1 an almost well-dominated graph. In this work, we first establish an upper bound for the cardinality of bipartite graphs with µ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.