{"entities":{"Q6964823":{"pageid":21292005,"ns":120,"title":"Item:Q6964823","lastrevid":84059567,"modified":"2026-05-09T01:30:27Z","type":"item","id":"Q6964823","labels":{"en":{"language":"en","value":"Recognizing relating edges in graphs without cycles of length 6"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8059021"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$2457D68E-7BB3-4DDD-9D07-D4EE226980D6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f06e69f06abbf74cf23f49cb9ebb75e2aa172212","datavalue":{"value":{"text":"Recognizing relating edges in graphs without cycles of length 6","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6964823$7163377A-CACC-4325-B607-E8E177C39177","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6eaa64efee4d045865a68e07e8fe2ee3afe232d6","datavalue":{"value":"1569.05281","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6964823$872D52E6-0180-4FE2-8DEB-094B85888F7A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c78d0ddb515d0b3b77b45652cc437b7a88d33676","datavalue":{"value":"10.1007/S00373-025-02930-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6964823$225EE932-9C59-4AF5-859C-1DB4CD6D1BDB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3379cff8d5e4805c5ff4f664fcb13704c759d836","datavalue":{"value":{"entity-type":"item","numeric-id":328718,"id":"Q328718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$36C53EEB-FF5E-4E0C-82CB-AFC1F29930AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5e34f5f64ac22b8c7ca91e00d4f03e6c5560edb3","datavalue":{"value":{"entity-type":"item","numeric-id":482208,"id":"Q482208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$1092900F-84C0-4DD9-97F3-A4EFA9007399","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$EF6C0CC0-5BFF-4F94-825E-2FED0E07EC42","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a0eb85789dff07e1672be2cc7f47985e7af00bf","datavalue":{"value":{"time":"+2025-07-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6964823$FAB2959D-A10F-4690-A0C8-58A810AD6E61","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"528a352165e0868c7c907b3bf1f28c8be5486765","datavalue":{"value":"A graph \\(G\\) is called well-covered if all its maximal independent sets are of the same cardinality. Let \\(w : V(G)\\rightarrow \\mathbb{R}\\) be a weight function. Then \\(G\\) is called \\(w\\)-well-covered if all its maximal independent sets are of the same weight. An edge \\(xy \\in E(G)\\) is relating if there exists \\(S \\subseteq V(G)\\) such that both \\(S \\cup \\{x\\}\\) and \\(S \\cup \\{y\\}\\) are maximal independent sets. If \\(xy\\) is relating then \\(w(x) = w(y)\\) for every weight function \\(w\\) such that \\(G\\) is \\(w\\)-well-covered. Relating edges are of crucial importance for investigating \\(w\\)-well-covered graphs. The problem of whether an edge is relating is NP-complete. The authors prove that this problem remains NP-complete even for graphs without cycles of length 6. A graph \\(G\\) is said to belong to the class \\(W_2\\) if every two pairwise disjoint independent sets in \\(G\\) are included in two pairwise disjoint maximum independent sets. A vertex \\(v \\in V(G)\\) is called shedding if for every independent set \\(S \\subseteq V(G) \\backslash N[v]\\) there exists \\(u \\in N(v)\\) such that \\(S\\cup \\{u\\}\\) is independent. Shedding vertices play an important role in studying the class \\(W_2\\), and recognizing shedding vertices is co-NP-complete. It was proved that this problem is co-NP-complete even for graphs without cycles of length 6. A conjecture concludes the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6964823$EAA251B8-9F8B-410C-B906-71EF6DD05C52","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$39F9DDCD-A5D6-48B2-A983-5433C42A4D10","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6964823$7249B2CA-7759-4952-904B-66F7E98DA010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6964823$A7A91904-6E09-4FEC-AC92-A9DBF3DB9961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6964823$A757441B-16EB-43C3-BFCA-A8D7C2335AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6964823$FC74B698-DA15-44DC-87B6-9DEC4A4AE11F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91e9609a25276ee88390dadd283cf29ce24f0ee4","datavalue":{"value":"8059021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6964823$8A0FE940-08AD-42D4-9F25-C750B3A1D1D0","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$AF025F92-294F-4C4E-915E-3E154787DC02","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95712ab71e3f2676f321e9a623c0ce37d7a08e3c","datavalue":{"value":"well-covered graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6964823$8B60F06E-261F-4EFA-9D61-375F0DFF06B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ae9d6409c02dc3b75b38ec625a7e97fcd160327","datavalue":{"value":"shedding vertex","type":"string"},"datatype":"string"},"type":"statement","id":"Q6964823$09DA393A-12B5-45AD-8984-555381F70AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7b3fcb7971813eba3091f9d059e9ca0ea6cae4c","datavalue":{"value":"relating edge","type":"string"},"datatype":"string"},"type":"statement","id":"Q6964823$B647097C-9146-4194-8FB0-50D5CF54975E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q6964823$01C7CBAE-9174-4E4A-9CAA-BC0E4114FD75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c6615ba0819e291b2e3e7c148f017134d814c6f","datavalue":{"value":"W2-graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6964823$BE330E71-516B-45C6-AB46-5641E9F92B54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"508def3536da451aaa16ab7a21353869c1e5bdc9","datavalue":{"value":"SAT problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6964823$35AFB711-AA20-43E9-8A42-53D9E9970FED","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$6838BB48-950C-4E76-B5EE-7F12D0837DA3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b6fbdf48d58da0f2c87f83a2858bbc874459c09","datavalue":{"value":{"entity-type":"item","numeric-id":2643318,"id":"Q2643318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$8A6F7517-C688-4458-9E42-4F80880EFF6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c66e9399d85a60fe702a3c8f638e9f3c77df7ac9","datavalue":{"value":{"entity-type":"item","numeric-id":4210230,"id":"Q4210230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$B19CE78D-FB92-432E-A8AF-8BA9C9E51EA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a633844813ff9727ac2e3dbbc37eb73f42deb90","datavalue":{"value":{"entity-type":"item","numeric-id":3139761,"id":"Q3139761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$C9952A25-4DB0-4B69-9FEA-ADBE3172506A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7909269b09c0147535000c5fb78b572b039d458e","datavalue":{"value":{"entity-type":"item","numeric-id":6201337,"id":"Q6201337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$F7EAEFA0-75AC-49F5-A41B-4A592372D635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22d112a283178f1892ecd85f7a067da210bdd426","datavalue":{"value":{"entity-type":"item","numeric-id":6988720,"id":"Q6988720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$A6867BCD-DE35-4F74-8655-291A3CCB1410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e363f33b9a6cdf7c6d902a4db962734cad449e0c","datavalue":{"value":{"entity-type":"item","numeric-id":1204485,"id":"Q1204485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$0EF651B4-8AFD-4094-841E-793BE2AF8D29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab56f8661476b22e55b635aac5664450e32f2175","datavalue":{"value":{"entity-type":"item","numeric-id":1690016,"id":"Q1690016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$70F1D151-2DBD-484B-B21B-7BA72033E873","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adb2d3fe1ecb0be7406a1505f1f3520741704399","datavalue":{"value":{"entity-type":"item","numeric-id":2311371,"id":"Q2311371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$0C36819D-0CCB-4380-801E-10D4B95FEDF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"514235266df6150f319fc41a88866bf471b0943e","datavalue":{"value":{"entity-type":"item","numeric-id":2447533,"id":"Q2447533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$C7B755C8-915E-4565-8B63-937EA64320C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d0e7f0c711117d25bb4fdf23bfeb7b3319d617b","datavalue":{"value":{"entity-type":"item","numeric-id":2345607,"id":"Q2345607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$77991ED6-1DA2-48B2-B70E-296A88AA89EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dad6a37009a443606e8cd74b3118607dd0db17cc","datavalue":{"value":{"entity-type":"item","numeric-id":724239,"id":"Q724239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$777CDA32-A623-4548-A85B-EAB2565A428B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08f51bb22ac5e91ad71d7b63f615df380509deb1","datavalue":{"value":{"entity-type":"item","numeric-id":6580488,"id":"Q6580488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$DB4D3F90-032D-444B-B0EA-8CE418429BA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f4a4b3bc5c191eb9820df0dcc0cef4c069d3c71","datavalue":{"value":{"entity-type":"item","numeric-id":3993632,"id":"Q3993632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$5E4DC6DA-AA1F-46BF-AFA4-D445BCB3FBB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eed0871e75da0af1c152f1e6236890fdf089fe9a","datavalue":{"value":{"entity-type":"item","numeric-id":4189306,"id":"Q4189306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$15EE0257-1166-4DF2-943C-290CCC7FDE44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a089f34aa5fb272606aec455414ecce311c0570e","datavalue":{"value":{"entity-type":"item","numeric-id":2192076,"id":"Q2192076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$8FF1341D-0497-4AE6-AE84-1FF898F3B2D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b078e45159479889c4a4838c50fbb8c93db95ae","datavalue":{"value":{"entity-type":"item","numeric-id":3182562,"id":"Q3182562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6964823$78FBAC46-B93E-4CA6-9D20-5C7D35023A5B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Recognizing relating edges in graphs without cycles of length 6","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Recognizing_relating_edges_in_graphs_without_cycles_of_length_6"}}}}}