DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

H. Alizadeh

Hadi Alizadeh

Gebze Technical University

email: halizadeh@gtu.edu.tr

D. Gözüpek

Didem Gözüpek

Department of Computer Engineering, Gebze Technical University

email: didem.gozupek@gtu.edu.tr

G. Boruzanli Ekinci

Gülnaz Boruzanli Ekinci

email: gulnaz.boruzanli@ege.edu.tr

Title:

$(C_3, C_4, C_5, C_7)$-free almost well-dominated graphs

PDF

Source:

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:

  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

Close