{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T09:40:08Z","timestamp":1748857208680,"version":"3.41.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T00:00:00Z","timestamp":1747440000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T00:00:00Z","timestamp":1747440000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100013043","name":"Ariel University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100013043","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,6]]},"abstract":"Abstract<\/jats:title>\n A graph G<\/jats:italic> is well-covered<\/jats:italic> if all its maximal independent sets are of the same cardinality. Let \n \n $$w:V(G) \\longrightarrow \\mathbb {R}$$<\/jats:tex-math>\n \n \n w<\/mml:mi>\n :<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n \u27f6<\/mml:mo>\n R<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> be a weight function. Then G<\/jats:italic> is w<\/jats:italic>-well-covered<\/jats:italic> if all its maximal independent sets are of the same weight. An edge \n \n $$xy \\in E(G)$$<\/jats:tex-math>\n \n \n x<\/mml:mi>\n y<\/mml:mi>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is relating<\/jats:italic> if there exists \n \n $$S \\subseteq V(G)$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n \u2286<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> such that both \n \n $$S \\cup \\{x\\}$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n \u222a<\/mml:mo>\n {<\/mml:mo>\n x<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and \n \n $$S \\cup \\{y\\}$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n \u222a<\/mml:mo>\n {<\/mml:mo>\n y<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> are maximal independent sets. If xy<\/jats:italic> is relating then \n \n $$ w(x)=w(y)$$<\/jats:tex-math>\n \n \n w<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n w<\/mml:mi>\n (<\/mml:mo>\n y<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> for every weight function w<\/jats:italic> such that G<\/jats:italic> is w<\/jats:italic>-well-covered. Relating edges are of crucial importance for investigating w<\/jats:italic>-well-covered graphs. The problem whether an edge is relating is NP-<\/jats:bold>complete. We prove that this problem remains NP-<\/jats:bold>complete even for graphs without cycles of length 6. A graph G<\/jats:italic> belongs to the class \n \n $$\\mathbf {W_{2}}$$<\/jats:tex-math>\n \n \n W<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> if every two pairwise disjoint independent sets in G<\/jats:italic> are included in two pairwise disjoint maximum independent sets. A vertex \n \n $$v \\in V(G)$$<\/jats:tex-math>\n \n \n v<\/mml:mi>\n \u2208<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is shedding<\/jats:italic> if for every independent set \n \n $$S \\subseteq V(G) \\setminus N[v]$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n \u2286<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n \\<\/mml:mo>\n N<\/mml:mi>\n [<\/mml:mo>\n v<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> there exists \n \n $$u \\in N(v)$$<\/jats:tex-math>\n \n \n u<\/mml:mi>\n \u2208<\/mml:mo>\n N<\/mml:mi>\n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> such that \n \n $$S \\cup \\{u\\}$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n \u222a<\/mml:mo>\n {<\/mml:mo>\n u<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is independent. Shedding vertices play an important role in studying the class \n \n $$\\mathbf {W_{2}}$$<\/jats:tex-math>\n \n \n W<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Recognizing shedding vertices is co-NP-<\/jats:bold>complete. We prove that this problem is co-NP-<\/jats:bold>complete even for graphs without cycles of length 6.<\/jats:p>","DOI":"10.1007\/s00373-025-02930-9","type":"journal-article","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T04:17:50Z","timestamp":1747455470000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Recognizing Relating Edges in Graphs Without Cycles of Length 6"],"prefix":"10.1007","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4190-7050","authenticated-orcid":false,"given":"Vadim E.","family":"Levit","sequence":"first","affiliation":[]},{"given":"David","family":"Tankus","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,17]]},"reference":[{"key":"2930_CR1","doi-asserted-by":"publisher","first-page":"2235","DOI":"10.1016\/j.disc.2006.10.011","volume":"307","author":"JI Brown","year":"2007","unstructured":"Brown, J.I., Nowakowski, R.J., Zverovich, I.E.: The structure of well-covered graphs with no cycles of length $$4$$. Discret. Math. 307, 2235\u20132245 (2007)","journal-title":"Discret. Math."},{"key":"2930_CR2","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1137\/S0895480196300479","volume":"11","author":"Y Caro","year":"1998","unstructured":"Caro, Y., Ellingham, N., Ramey, G.F.: Local structure when all maximal independent sets have equal weight. SIAM J. Discret. Math. 11, 644\u2013654 (1998)","journal-title":"SIAM J. Discret. Math."},{"key":"2930_CR3","first-page":"179","volume-title":"A note on well-covered graphs, Quo vadis, Graph Theory Ann Discr Math 55","author":"V Chvatal","year":"1993","unstructured":"Chvatal, V., Slater, P.J.: A note on well-covered graphs, Quo vadis, Graph Theory Ann Discr Math 55, pp. 179\u2013182. North Holland, Amsterdam (1993)"},{"key":"2930_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.114403","volume":"990","author":"C Feghali","year":"2024","unstructured":"Feghali, C., Marin, M.: Three remarks on $$W_{2}$$ graphs. Theoret. Comput. Sci. 990, 114403 (2024)","journal-title":"Theoret. Comput. Sci."},{"key":"2930_CR5","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-031-75409-8_13","volume":"14760","author":"C Feghali","year":"2025","unstructured":"Feghali, C., Marin, M., Watrigant, R.: Beyond recognizing well-covered graphs. Lect. Notes Comput. Sci. 14760, 181\u2013195 (2025)","journal-title":"Lect. Notes Comput. Sci."},{"key":"2930_CR6","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1006\/jctb.1993.1005","volume":"57","author":"A Finbow","year":"1993","unstructured":"Finbow, A., Hartnell, B., Nowakowski, R.: A characterization of well-covered graphs of girth $$5$$ or greater. J. Combin. Theory Ser. B. 57, 44\u201368 (1993)","journal-title":"J. Combin. Theory Ser. B."},{"key":"2930_CR7","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"key":"2930_CR8","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1016\/j.endm.2017.07.038","volume":"61","author":"VE Levit","year":"2017","unstructured":"Levit, V.E., Mandrescu, E.: $$W_{2}$$-graphs and shedding vertices. Electron. Notes Discrete Math. 61, 797\u2013803 (2017)","journal-title":"Electron. Notes Discrete Math."},{"key":"2930_CR9","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/j.ejc.2018.02.021","volume":"80","author":"VE Levit","year":"2019","unstructured":"Levit, V.E., Mandrescu, E.: $$1$$-well-covered graphs revisited. Eur. J. Comb. 80, 261\u2013272 (2019)","journal-title":"Eur. J. Comb."},{"key":"2930_CR10","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.jda.2013.09.007","volume":"26","author":"VE Levit","year":"2014","unstructured":"Levit, V.E., Tankus, D.: On relating edges in graphs without cycles of length $$4$$. J. Discrete Algor. 26, 28\u201333 (2014)","journal-title":"J. Discrete Algor."},{"key":"2930_CR11","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.dam.2015.01.001","volume":"186","author":"VE Levit","year":"2015","unstructured":"Levit, V.E., Tankus, D.: Well-covered graphs without cycles of lengths $$4$$, $$5$$ and $$6$$. Discret. Appl. Math. 186, 158\u2013167 (2015)","journal-title":"Discret. Appl. Math."},{"key":"2930_CR12","doi-asserted-by":"publisher","first-page":"2384","DOI":"10.1007\/s00453-017-0325-1","volume":"80","author":"VE Levit","year":"2018","unstructured":"Levit, V.E., Tankus, D.: Complexity results for generating subgraphs. Algorithmica 80, 2384\u20132399 (2018)","journal-title":"Algorithmica"},{"key":"2930_CR13","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/s00373-024-02777-6","volume":"40","author":"VE Levit","year":"2024","unstructured":"Levit, V.E., Tankus, D.: Recognizing $$W_{2}$$ graphs. Graphs Combin. 40, 72 (2024)","journal-title":"Graphs Combin."},{"key":"2930_CR14","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1002\/net.3230220304","volume":"22","author":"RS Sankaranarayana","year":"1992","unstructured":"Sankaranarayana, R.S., Stewart, L.K.: Complexity results for well-covered graphs. Networks 22, 247\u2013262 (1992)","journal-title":"Networks"},{"key":"2930_CR15","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1002\/jgt.3190030211","volume":"3","author":"JW Staples","year":"1979","unstructured":"Staples, J.W.: On some subclasses of well-covered graphs. J. Graph Theory 3, 197\u2013204 (1979)","journal-title":"J. Graph Theory"},{"key":"2930_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.dam.2020.01.012","volume":"283","author":"D Tankus","year":"2020","unstructured":"Tankus, D.: Recognizing generating subgraphs in graphs without cycles of lengths $$6$$ and $$7$$. Discret. Appl. Math. 283, 189\u2013198 (2020)","journal-title":"Discret. Appl. Math."},{"key":"2930_CR17","doi-asserted-by":"publisher","first-page":"3235","DOI":"10.1090\/S0002-9939-09-09981-X","volume":"137","author":"R Woodroofe","year":"2009","unstructured":"Woodroofe, R.: Vertex decomposable graphs and obstructions to shellability. Proc. Am. Math. Soc. 137, 3235\u20133246 (2009)","journal-title":"Proc. Am. Math. Soc."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02930-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02930-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02930-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T09:15:43Z","timestamp":1748855743000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02930-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,17]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["2930"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02930-9","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2025,5,17]]},"assertion":[{"value":"8 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"69"}}