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 $$(G) = Γ(G) − Γ(G). While a graph G with $$(G) = 0 is said to be a well-dominated graph, we call a graph G with $$(G) = 1 an almost well-dominated graph. In this work, we first establish an upper bound for the cardinality of bipartite graphs with $$(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.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2020042
Keywords: Bipartite graphs, domination gap, well-dominated graphs, almost well-dominated graphs
@article{RO_2021__55_S1_S1633_0,
author = {Alizadeh, Hadi and G\"oz\"upek, Didem},
title = {Almost well-dominated bipartite graphs with minimum degree at least two},
journal = {RAIRO. Operations Research},
pages = {S1633--S1646},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ro/2020042},
mrnumber = {4223130},
zbl = {1469.05124},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020042/}
}
TY - JOUR AU - Alizadeh, Hadi AU - Gözüpek, Didem TI - Almost well-dominated bipartite graphs with minimum degree at least two JO - RAIRO. Operations Research PY - 2021 SP - S1633 EP - S1646 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020042/ DO - 10.1051/ro/2020042 LA - en ID - RO_2021__55_S1_S1633_0 ER -
%0 Journal Article %A Alizadeh, Hadi %A Gözüpek, Didem %T Almost well-dominated bipartite graphs with minimum degree at least two %J RAIRO. Operations Research %D 2021 %P S1633-S1646 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020042/ %R 10.1051/ro/2020042 %G en %F RO_2021__55_S1_S1633_0
Alizadeh, Hadi; Gözüpek, Didem. Almost well-dominated bipartite graphs with minimum degree at least two. RAIRO. Operations Research, Tome 55 (2021), pp. S1633-S1646. doi: 10.1051/ro/2020042
, and , Graphs with two sizes of minimal dominating sets. Congr. Numer. 111 (1995) 115–128. | MR | Zbl
, and , Well-dominated graphs: a collection of well-covered ones. Ars Comb. 25A (1988) 5–10. | MR | Zbl
, and , A revision and extension of results on 4-regular, 4-connected, claw-free graphs. Disc. Appl. Math. 159 (2011) 1225–1230. | MR | Zbl | DOI
, and , Fundamentals of Domination in Graphs. In Vol. 208 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, New York, NY (1998). | MR | Zbl
, Characterizing a subclass of well-covered graphs. Congr. Numer. 160 (2003) 7–31. | MR | Zbl
and , Well-dominated graphs without cycles of lengths 4 and 5. Disc. Math. 340 (2017) 1793–1801. | MR | Zbl | DOI
and , Domination in graphs with minimum degree two. J. Graph Theory 13 (1989) 749–762. | MR | Zbl | DOI
, Paths, stars and the number three. Comb. Probab. Comput. 5 (1996) 277–295. | MR | Zbl | DOI
and , Well covered and well dominated block graphs and unicyclic graphs. Math. Pannonica 1 (1990) 55–66. | MR | Zbl
and , Locally well-dominated and locally independent well-dominated graphs. Graphs Comb. 19 (2003) 279–288. | MR | Zbl | DOI
Cité par Sources :
