Article in volume
Authors:
Title:
$(C_3, C_4, C_5, C_7)$-free almost well-dominated graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1099-1117
Received: 2019-05-27 , Revised: 2020-05-07 , Accepted: 2020-05-09 , Available online: 2020-05-27 , https://doi.org/10.7151/dmgt.2331
Abstract:
The domination gap of a graph $G$ is defined as the difference 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 ($C_3,C_4,C_5,C_7$)-free almost well-dominated graphs
by giving a complete structural characterization for such graphs.
Keywords:
well-dominated graphs, almost well-dominated graphs, domination gap
References:
- J.E. Dunbar, L. Markus and D. Rall, Graphs with two sizes of minimal dominating sets, Congr. Numer. 111 (1995) 115-128.
- 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 - B. Finbow, A. Hartnell and R. Nowakowski, Well-dominated graphs: A collection of well-covered ones, Ars Combin. 25 (1988) 5–10.
- 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 - 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 - 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 - 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 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
- E.L.C. King, Characterizing a subclass of well-covered graphs, Congr. Numer. 160 (2003) 7–31.
- 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 - J. Topp and L. Volkmann, Well covered and well dominated block graphs and unicyclic graphs, Math. Pannon. 1(2) (1990) 55–66.
- 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
Close