Volume 55, 2021Regular articles published in advance of the transition of the journal to Subscribe to Open (S2O). Free supplement sponsored by the Fonds National pour la Science Ouverte
|Page(s)||S1633 - S1646|
|Published online||02 March 2021|
Almost well-dominated bipartite graphs with minimum degree at least two
Department of Computer Engineering, Gebze Technical University, Kocaeli, Turkey
* Corresponding author: email@example.com
Accepted: 23 April 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.
Mathematics Subject Classification: 05C69 / 05C75 / 68R10
Key words: Bipartite graphs / domination gap / well-dominated graphs / almost well-dominated graphs
© EDP Sciences, ROADEF, SMAI 2021
Initial download of the metrics may take a while.