{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:07Z","timestamp":1740144487179,"version":"3.37.3"},"reference-count":20,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T00:00:00Z","timestamp":1718668800000},"content-version":"vor","delay-in-days":48,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,5,10]]},"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:p>Let<jats:italic>G<\/jats:italic>be a graph. If<jats:italic>G<\/jats:italic>has exactly<jats:italic>r<\/jats:italic>distinct sizes of maximal independent sets,<jats:italic>G<\/jats:italic>belongs to a collection called<jats:italic>M<jats:sub>r<\/jats:sub><\/jats:italic>. If<jats:italic>G<\/jats:italic>\u2208<jats:italic>M<jats:sub>r<\/jats:sub><\/jats:italic>and the distinct values of its maximal independent sets are consecutive, then<jats:italic>G<\/jats:italic>belongs to<jats:italic>I<jats:sub>r<\/jats:sub><\/jats:italic>. The independence gap of<jats:italic>G<\/jats:italic>is the difference between the maximum and the minimum sizes of a maximal independent set in<jats:italic>G<\/jats:italic>. In this paper, we show that recognizing graphs in<jats:italic>I<jats:sub>r<\/jats:sub><\/jats:italic>is NP-complete, for every integer<jats:italic>r<\/jats:italic>\u2265 3. On the other hand, we show that recognizing trees in<jats:italic>M<jats:sub>r<\/jats:sub><\/jats:italic>can be done in polynomial time, for every<jats:italic>r<\/jats:italic>\u2265 1. Furthermore, we present characterizations of some graphs with girth at least 6 with independence gap at least 1, including graphs with independence gap<jats:italic>r<\/jats:italic>\u2212 1, for<jats:italic>r<\/jats:italic>\u2265 2, belonging to<jats:italic>I<jats:sub>r<\/jats:sub><\/jats:italic>. Moreover, we present a characterization of some trees in<jats:italic>I<\/jats:italic><jats:sub>3<\/jats:sub>.<\/jats:p>","DOI":"10.1051\/ro\/2024110","type":"journal-article","created":{"date-parts":[[2024,5,15]],"date-time":"2024-05-15T08:24:45Z","timestamp":1715761485000},"page":"2379-2391","source":"Crossref","is-referenced-by-count":0,"title":["Distinct sizes of maximal independent sets on graphs with restricted girth"],"prefix":"10.1051","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1888-7802","authenticated-orcid":false,"given":"M\u00e1rcia","family":"Cappelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3002-5172","authenticated-orcid":false,"given":"Julliano","family":"Nascimento","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vin\u00edcius","family":"Santos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,6,18]]},"reference":[{"key":"R1","first-page":"115","volume":"01","author":"Barbosa","year":"1998","journal-title":"Congr. Numer."},{"key":"R2","doi-asserted-by":"crossref","first-page":"1630","DOI":"10.1016\/j.disc.2013.04.019","volume":"313","author":"Barbosa","year":"2013","journal-title":"Discrete Math."},{"doi-asserted-by":"crossref","unstructured":"Bondy J.A. and Murty U.S.R., Graph Theory with Applications. Elsevier, New York (1976).","key":"R3","DOI":"10.1007\/978-1-349-03521-2"},{"key":"R4","doi-asserted-by":"crossref","first-page":"2742","DOI":"10.1016\/j.disc.2013.08.016","volume":"313","author":"Cappelle","year":"2013","journal-title":"Discrete Math."},{"unstructured":"Cappelle M.R., Dias M.C. and Santos V.G., Independence gap in graphs of girth at least 6. In: Anais do Simp\u00f3sio Brasileiro de Pesquisa Operacional (2020).","key":"R5"},{"key":"R6","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jagm.1996.0006","volume":"20","author":"Caro","year":"1996","journal-title":"J. Algorithms"},{"key":"R7","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0167-5060(08)70387-X","volume":"55","author":"Chv\u00e1tal","year":"1993","journal-title":"Ann. Discrete Math."},{"key":"R8","doi-asserted-by":"crossref","first-page":"2817","DOI":"10.3906\/mat-2105-45","volume":"45","author":"Deniz","year":"2021","journal-title":"Turk. J. Math."},{"unstructured":"Ekim T., G\u00f6z\u00fcpek D., Hujdurovi\u0107 A., and Milani\u010d M., On Almost Well-Covered Graphs of Girth at Least 6. Discrete Math. Theor. Comput. Sci. 20 (2018).","key":"R9"},{"key":"R10","first-page":"189","volume":"16","author":"Finbow","year":"1983","journal-title":"Ars Comb."},{"key":"R11","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1006\/jctb.1993.1005","volume":"57","author":"Finbow","year":"1993","journal-title":"J. Comb. Theory Ser. B"},{"key":"R12","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0012-365X(94)90156-2","volume":"125","author":"Finbow","year":"1994","journal-title":"Discrete Math."},{"key":"R13","first-page":"107","volume":"29","author":"Hartnell","year":"1999","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"R14","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/s00373-012-1132-8","volume":"29","author":"Hartnell","year":"2013","journal-title":"Graphs and Combin."},{"key":"R15","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s40687-022-00326-2","volume":"9","author":"Kimura","year":"2022","journal-title":"Res. Math. Sci."},{"key":"R16","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0021-9800(70)80011-4","volume":"8","author":"Plummer","year":"1970","journal-title":"J. Comb. Theory"},{"key":"R17","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1080\/16073606.1993.9631737","volume":"16","author":"Plummer","year":"1993","journal-title":"Quaest. Math."},{"key":"R18","first-page":"20","volume":"2","author":"Ravindra","year":"1977","journal-title":"J. Comb. Inf. Syst. Sci."},{"unstructured":"Sankaranarayana R.S. and Stewart L.K., Complexity results for well-covered graphs. J. Comb. Inf. Syst. Sci. (1997).","key":"R19"},{"unstructured":"Staples J., On Some Subclasses of Well-Covered Graphs. Ph.D. thesis, Vanderbilt University (1975).","key":"R20"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024110\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T01:54:18Z","timestamp":1731981258000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5]]},"references-count":20,"journal-issue":{"issue":"3"},"alternative-id":["ro240024"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024110","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,5]]}}}