{"entities":{"Q2643318":{"pageid":2654061,"ns":120,"title":"Item:Q2643318","lastrevid":50150951,"modified":"2026-01-13T06:58:01Z","type":"item","id":"Q2643318","labels":{"en":{"language":"en","value":"The structure of well-covered graphs with no cycles of length 4"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5182387"}},"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":"Q2643318$54A91CCA-9E9C-48D8-8A0B-28B179FB158A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bb44610031f345e6429e91f392a9f4292c9d4119","datavalue":{"value":{"text":"The structure of well-covered graphs with no cycles of length 4","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2643318$3C16463A-2059-48EA-852A-B419677FDDD1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5588bced86b991289a860e56c3bdd2c37bdd029e","datavalue":{"value":"1127.05068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643318$E9871718-A8BE-4716-AFAD-E7374AAE98EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a68a3f89d9aea1235cfd922d12cd03ef17d4d8b","datavalue":{"value":{"entity-type":"item","numeric-id":343710,"id":"Q343710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$01853BD2-6547-4EAF-9303-ABE907C8FD08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5676fa5282611dbd0fab8edb7a4f82cf8ae7a025","datavalue":{"value":{"entity-type":"item","numeric-id":215016,"id":"Q215016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$5FF3A9A2-B940-43D8-9262-E7DC6EC2CE83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"966cac424910391b9527b89169a088f18b0794d7","datavalue":{"value":{"entity-type":"item","numeric-id":704847,"id":"Q704847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$7B12DD78-873E-4A0E-A49F-DF0C3D02E14F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$4A3AE5E3-82EC-47CF-A123-0785C5ED9CB9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"226fad3e536b676c763bdce84a93ee9c766c4ae5","datavalue":{"value":{"time":"+2007-08-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2643318$387A6FA7-8C92-418D-BA64-22B62E04365D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"220217f35319951b134b7758bc8a55fff495ca02","datavalue":{"value":"Let \\(G\\) be a finite, simple graph with vertex set \\(V(G)\\), let \\({I}(G)\\) be the set of all maximal independent sets in \\(G\\) and let \\(\\alpha(G)=\\max\\{| I| :I \\in {I}(G)\\}\\) denote the independence number of \\(G\\). Call \\(G\\) well-covered if \\(| I| =\\alpha(G)\\) for each \\(I \\in {I}(G)\\). Also let \\(f:V(G) \\rightarrow \\mathbb R\\) be a weighting of \\(G\\) which itself is well-covered if there is some value \\(K\\) such that \\(\\sum_{x \\in M} f(x) = K\\) for each \\(M \\in {I}(G)\\).   This paper studies the class WC\\((\\widehat{C_{4}})\\) of well-covered graphs with no cycles of length 4. The main result is that if \\(G \\in \\text{WC}(\\widehat{C_{4}})\\) then \\(V(G)\\) can be partitioned, using an equivalence relation, into subsets \\(V_{1}, \\dots, V_{k}\\) such that (i) each induced subgraph \\(G[V_{i}]\\) is well-covered, (ii) \\(\\sum_{i=1}^{k} \\alpha(G[V_{i}]) = \\alpha(G)\\), and (iii) the vector space of the well-covered weightings of \\(G\\) is the direct sum of the vector spaces of the well-covered weightings of the \\(G[V_{i}]\\), each of which has dimension 1.   The second result is that the problem of determining whether an edge of a graph is incident with two vertices in the same equivalence class is NP-complete. The authors give a forbidden co-stable subgraph characterization of graphs in WC\\((\\widehat{C_{4}})\\). Finally, they prove that graphs in WC\\((\\widehat{C_{4}})\\) of bounded maximum generalized degree can be recognized in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643318$491730B8-AE93-4F83-B61D-4A94B1D3A7C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643318$061215E3-4D6A-4CC4-8938-5978A15CB1E0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8cfe9f354ec4af66528a1eab2e0a5a828b3d95f9","datavalue":{"value":"5182387","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643318$80F994AA-FD07-496F-86CF-157772C81CD1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95712ab71e3f2676f321e9a623c0ce37d7a08e3c","datavalue":{"value":"well-covered graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643318$CFA493DE-CE3C-4677-BBF6-92515CC97064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643318$B59B69D4-FFB3-4846-B1E8-20E27F45E908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b110a7ada151f303fcee79af76f11497f31c8d0","datavalue":{"value":"well-covered weighting","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643318$15CCA258-A96F-4764-B4FF-FDD6572053DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bfbdacd2237eb430da08e5396101c8d61621d00a","datavalue":{"value":"\\(C_4\\)-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643318$3473EF1D-BF69-4862-B85D-E415CCAFF215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5caf09f23a5bd44601ef1b376fd6cba9845252d5","datavalue":{"value":"vector space","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643318$A8FEFB52-CE78-4CF9-9CDA-74141C84CCB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a684056d7eccd263bb794c8093e79ef7113b9bb6","datavalue":{"value":"forbidden co-stable subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643318$B6819CEF-E0BE-4CF7-B920-E18C67D72BD7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a45b400d22190ce8d9d8376830240adc5a55cd78","datavalue":{"value":{"entity-type":"item","numeric-id":367043,"id":"Q367043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$4CD21BF2-7B9D-4619-AFDE-14310914E804","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":"Q2643318$FF712850-A771-4849-A4BD-5B8FBA6282BD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b63c68582fa90f867af43f4ed684b746ec8381c3","datavalue":{"value":"https://doi.org/10.1016/j.disc.2006.10.011","type":"string"},"datatype":"url"},"type":"statement","id":"Q2643318$0F1A4A30-D04A-4852-8ED9-F7EDE48D9254","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b5bfcea1064e2b818a2af582216e5e9d691844dc","datavalue":{"value":"W1997658699","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643318$0BC0B701-6D1E-48F2-A37C-1DB0073F4483","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"11673dcd21853f951527c7496c4c07b5798247bf","datavalue":{"value":{"entity-type":"item","numeric-id":5470803,"id":"Q5470803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$9A2E6E55-90C8-4598-A6EA-235E404B559A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b48ffc227321e403ea755df51d696c4b05484a1f","datavalue":{"value":{"entity-type":"item","numeric-id":4693382,"id":"Q4693382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$DA9189F6-A682-48D7-9CD8-3B7755222B8F","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":"Q2643318$9423406F-07ED-4A0B-9C58-37EAD097A81D","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":"Q2643318$A2E9943A-1EE8-4813-8A54-B902A7ED2974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97f9741b8d6af618c79b712f064a8343d5d6c6c0","datavalue":{"value":{"entity-type":"item","numeric-id":1318795,"id":"Q1318795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$4212D5FC-1EFB-40CE-90E8-12727DAA4ED6","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":"Q2643318$D9732814-EC03-427E-BECE-964674AB0901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f11e90ea00829135a7cf52daf60340227f0e8500","datavalue":{"value":{"entity-type":"item","numeric-id":4312248,"id":"Q4312248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$347852A3-C3FF-4C99-833C-51C2D96EF9DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa275c1c1e3e321551d7d097e448391210bbab97","datavalue":{"value":{"entity-type":"item","numeric-id":4697570,"id":"Q4697570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$62A6D7A3-DA22-47F8-8225-220A9C3382A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95cfc8d4bd86e9a748b7fc1ca1208d833f2bfa25","datavalue":{"value":{"entity-type":"item","numeric-id":5591382,"id":"Q5591382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$D9EDE63A-3B14-47D6-9C6E-BCD7E6FC37DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a81383721f4874d6a884871511fbd6173e2829d","datavalue":{"value":{"entity-type":"item","numeric-id":4288045,"id":"Q4288045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$CF4196CC-3AF1-445D-8E7F-AE7C132043C2","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":"Q2643318$A29C9E79-1CBE-48A2-85EE-4FE9A45853D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bfcf49bbdf6cc8c99331f55277badec861e8121","datavalue":{"value":{"entity-type":"item","numeric-id":1354731,"id":"Q1354731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$BDE65328-F9C9-4DFB-A9BD-E355A4F4F304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3896fdd8fbf603cb9a633fa15904a33e25a1a6b3","datavalue":{"value":{"entity-type":"item","numeric-id":1581458,"id":"Q1581458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643318$F7D444FE-4A32-4026-B5AE-8C2B3991683B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0e60f97ec6b660b6aa461f08242e0d62d6150ceb","datavalue":{"value":"10.1016/J.DISC.2006.10.011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643318$22895E9B-2C17-4F7A-A2A8-F259A1B5A73F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed996575216dbf00a80f4c47f222846caa9f4d06","datavalue":{"value":{"entity-type":"item","numeric-id":4312248,"id":"Q4312248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"adea353f8aa18c62b06a45aac5b8cca69d80e49e","datavalue":{"value":{"amount":"+0.8733225464820862","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2643318$FBC2E55F-3334-4180-BB1C-5970C9C2F0A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3149a991e0b0f3c69e5e724e847ae1357136e3cd","datavalue":{"value":{"entity-type":"item","numeric-id":4210230,"id":"Q4210230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc099764bf01db0f2fd3323f3840c2424b331dd0","datavalue":{"value":{"amount":"+0.8697043657302856","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2643318$4839637A-272E-49A2-AF3D-D78FC5650023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cda1efbde989537439b7d46a1e58b6c3a84e048","datavalue":{"value":{"entity-type":"item","numeric-id":628320,"id":"Q628320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"340991c2c37209353e320837703285873b5ecb86","datavalue":{"value":{"amount":"+0.8693057894706726","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2643318$48C42546-964B-44B4-933B-7428AA4FCAF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd556473550b7685d46a88bab1c2a2bceb57d27e","datavalue":{"value":{"entity-type":"item","numeric-id":3655148,"id":"Q3655148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4fabd172e13aa8fc8fdbd035a9dadf5079a43ca","datavalue":{"value":{"amount":"+0.860853374004364","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2643318$9191076F-D935-4D6C-A24E-96ED7B88009B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d837887575861f75d86eda5ede420a4782133ddc","datavalue":{"value":{"entity-type":"item","numeric-id":4940016,"id":"Q4940016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bc73746b5bab15bd761bf08bc8d0941a46628f1","datavalue":{"value":{"amount":"+0.8567202687263489","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2643318$0B326255-DDB9-47DD-8CC3-480EAEA8C4BA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2643318","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2643318"}}}}}