Geodesic
(C3, C4, C5, C7)-Free Almost Well-Dominated Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1099-1117.

Voir la notice de l'article provenant de la source Library of Science

The domination gap of a graph G is defined as the di erence between the maximum and minimum cardinalities of a minimal dominating set in G. The term well-dominated graphs referring to the graphs with domination gap zero, was first introduced by Finbow et al. [Well-dominated graphs: A collection of well-covered ones, Ars Combin. 25 (1988) 5–10]. In this paper, we focus on the graphs with domination gap one which we term almost well-dominated graphs. While the results by Finbow et al. have implications for almost well-dominated graphs with girth at least 8, we extend these results to (C3, C4, C5, C7)-free almost well-dominated graphs by giving a complete structural characterization for such graphs.
Keywords: well-dominated graphs, almost well-dominated graphs, domination gap 
@article{DMGT_2022_42_4_a5,
     author = {Alizadeh, Hadi and G\"oz\"upek, Didem and Ekinci, G\"ulnaz Boruzanl{\i}},
     title = {(C\protect\textsubscript{3}, {C\protect\textsubscript{4},} {C\protect\textsubscript{5},} {C\protect\textsubscript{7})-Free} {Almost} {Well-Dominated} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1099--1117},
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a5/}
}
TY  - JOUR
AU  - Alizadeh, Hadi
AU  - Gözüpek, Didem
AU  - Ekinci, Gülnaz Boruzanlı
TI  - (C3, C4, C5, C7)-Free Almost Well-Dominated Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1099
EP  - 1117
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a5/
LA  - en
ID  - DMGT_2022_42_4_a5
ER  - 
%0 Journal Article
%A Alizadeh, Hadi
%A Gözüpek, Didem
%A Ekinci, Gülnaz Boruzanlı
%T (C3, C4, C5, C7)-Free Almost Well-Dominated Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1099-1117
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a5/
%G en
%F DMGT_2022_42_4_a5
Alizadeh, Hadi; Gözüpek, Didem; Ekinci, Gülnaz Boruzanlı. (C3, C4, C5, C7)-Free Almost Well-Dominated Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1099-1117. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a5/

[1] J.E. Dunbar, L. Markus and D. Rall, Graphs with two sizes of minimal dominating sets, Congr. Numer. 111 (1995) 115-128.

[2] T. Ekim, D. Gözüpek, A. Hujdurović and M. Milanič, Almost well-covered graphs of girth at least 6, Discrete Math. Theor. Comput. Sci. 20 (2018). https://doi.org/10.23638/DMTCS-20-2-17

[3] B. Finbow, A. Hartnell and R. Nowakowski, Well-dominated graphs: A collection of well-covered ones, Ars Combin. 25 (1988) 5–10.

[4] A. Finbow, B. Hartnell and R.J. Nowakowski, A characterization of well covered graphs of girth 5 or greater, J. Combin. Theory Ser. B 57 (1993) 44–68. https://doi.org/10.1006/jctb.1993.1005

[5] A. Finbow, B. Hartnell and R.J. Nowakowski, A characterization of well-covered graphs that contain neither 4 -nor 5 -cycles, J. Graph Theory 18 (1994) 713–721. https://doi.org/10.1002/jgt.3190180707

[6] A. Finbow, B. Hartnell and C. Whitehead, A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets, Discrete Math. 125 (1994) 153–167. https://doi.org/10.1016/0012-365X(94)90156-2

[7] T.J. Gionet, E.L.C. King and Y. Sha, A revision and extension of results on 4- regular, 4 -connected, claw-free graphs, Discrete Appl. Math. 159 (2011) 1225–1230. https://doi.org/10.1016/j.dam.2011.04.013

[8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).

[9] E.L.C. King, Characterizing a subclass of well-covered graphs, Congr. Numer. 160 (2003) 7–31.

[10] V.E. Levit and D. Tankus, Well-dominated graphs without cycles of lengths 4 and 5, Discrete Math. 340 (2017) 1793–1801. https://doi.org/10.1016/j.disc.2017.02.021

[11] J. Topp and L. Volkmann, Well covered and well dominated block graphs and unicyclic graphs, Math. Pannon. 1(2) (1990) 55–66.

[12] I.E. Zverovich and V.E. Zverovich, Locally well-dominated and locally independent well-dominated graphs, Graphs Combin. 19 (2003) 279–288. https://doi.org/10.1007/s00373-002-0507-7