1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

(C3, C4, C5, C7)-Free Almost Well-Dominated Graphs

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1099 - 1117
Received: 27 May 2019
Accepted: 09 May 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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

MSC 2010

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

[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 Search in Google Scholar

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

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

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

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

[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 Search in Google Scholar

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

[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 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo