{"entities":{"Q5936038":{"pageid":8112840,"ns":120,"title":"Item:Q5936038","lastrevid":41928459,"modified":"2025-05-16T12:37:55Z","type":"item","id":"Q5936038","labels":{"en":{"language":"en","value":"Characterization of \\(Z_m\\)-well-covered graphs for some classes of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1612898"}},"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":"Q5936038$F3B2DE6D-90B6-4D97-A9F3-EC2754365566","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"381e3ae783791e8507fd8dfce22bd29ea668c77e","datavalue":{"value":{"text":"Characterization of \\(Z_m\\)-well-covered graphs for some classes of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5936038$75992FE6-40A1-4254-997C-924F73B73B88","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cf52700510a93ca41d40031159a2bd2ac12a125e","datavalue":{"value":"0988.05080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936038$1E66355B-847D-46B0-A7AC-8EBFDC372216","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"60e7eb123886db55ff3dfdc88e712e4be4983d71","datavalue":{"value":"10.1016/S0012-365X(00)00247-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936038$D3FD9412-A2E0-499E-AF05-261932CA2C0A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"27f25b51b7c2d10041017266dbb39a414d31b84c","datavalue":{"value":{"entity-type":"item","numeric-id":412266,"id":"Q412266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936038$A72290D6-41A2-448D-AEF1-C8740C63383E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c28117db9c7e125c64a62279c5126736944bfba","datavalue":{"value":{"entity-type":"item","numeric-id":323040,"id":"Q323040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936038$FE4E5EDA-318B-4324-8145-933008B2720E","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":"Q5936038$2E38F954-4E52-4DAE-A497-0066523536A9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d25d55580aa033c3456b22cc344777f6eb808095","datavalue":{"value":{"time":"+2002-06-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5936038$731DE53A-C35F-460D-89E6-5E496632CC60","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936038$7358EDAC-CA2E-4692-A4DB-95B447234E73","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936038$26D4D7DB-4272-44DC-B9A6-2CC5BFE664B9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1075e1f36625c37861dddce37aac58b9cb5f4cd2","datavalue":{"value":"1612898","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936038$01EC13FC-3DC8-4126-B392-DD1A5481591E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abdf3a1bda0112785fb25f1045b4779fda268c71","datavalue":{"value":"simplicial graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936038$14844931-CF97-4EE4-86FE-070F042C036A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae41303426e6695786e3a6d28699919bfeab34a","datavalue":{"value":"chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936038$42B4EA04-F771-4D39-9B9F-D0801630E660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e1780000149a6841fc7293614b6f16c5ba3a690","datavalue":{"value":"circular arc graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936038$DA941D55-436E-42E6-82E4-4022ECFC2DBE","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":"Q5936038$28046F51-55FE-4F91-979D-BA908E0D9C08","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"44bc351aaaaba6688b50ee2f6bed9cfa50680ed8","datavalue":{"value":"Q126648983","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936038$8A6F3792-1706-4A60-8A3A-49D0EBA8CDEA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"43844227b637b2bcb448ac3924e1c12933f64f30","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00247-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q5936038$D93F9AB1-6A78-4850-A209-74355AF4C1CE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"83c8b7ff1fd69ef4a537ab50a179dafa75d62172","datavalue":{"value":"W2037821860","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936038$92DDCF52-AE2B-4073-8C89-97CBFEBA83D2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5cf27a2aad08ff5573f47ab40dd765e32055c7c","datavalue":{"value":{"entity-type":"item","numeric-id":4948753,"id":"Q4948753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"880bca74295ef035f4c6f5266de9377b2c0ef7c4","datavalue":{"value":{"amount":"+0.93254274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936038$EE68E497-B027-474A-9566-472D74075CBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b79f021234adee42ea12eae410b14de97caacd8","datavalue":{"value":{"entity-type":"item","numeric-id":4464779,"id":"Q4464779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cccbbe998296d8eafb2d4ed549d4d66828afab0f","datavalue":{"value":{"amount":"+0.9155587","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936038$B2C4A740-2767-47FF-B796-28CB9E9D3FA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3755b58d7ae18c7afab0b8fbd90dbb6933c1534f","datavalue":{"value":{"entity-type":"item","numeric-id":2715989,"id":"Q2715989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6909c01fae3a9233edf1304f073cb94e342532f8","datavalue":{"value":{"amount":"+0.90843326","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936038$7FD1DE22-495E-4078-BC64-ACD00398C537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80342e10b3ba653b2c8a2b684bbbd4535b0263bc","datavalue":{"value":{"entity-type":"item","numeric-id":4691635,"id":"Q4691635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48f056ee25611f52a1ceb665d8f46cc4d05cedc2","datavalue":{"value":{"amount":"+0.8868326","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936038$FC975F16-3159-44CA-9A02-8A201AF23886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e96cd6c031a3636139d3023bb6bac50a1eb3a865","datavalue":{"value":{"entity-type":"item","numeric-id":1581458,"id":"Q1581458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"537069414d45c9bc45a8fdfe2e3b88cddf63a386","datavalue":{"value":{"amount":"+0.88352513","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936038$CD0E240A-6159-4EBB-B69F-820E132274E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"368c2b013b84cecfaecbe8e5363878ec90a00ffa","datavalue":{"value":{"entity-type":"item","numeric-id":3981346,"id":"Q3981346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c315789f6b6eb41ee18e97229a77e0dc3922194","datavalue":{"value":{"amount":"+0.8817752","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936038$DBB3ABEC-87D5-4E85-ACDC-26328B19C541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8387b68c54e65cc9a86e97b274bb0a33dbca082","datavalue":{"value":{"entity-type":"item","numeric-id":5443167,"id":"Q5443167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cffef8b9c19d5da5b252640a2ab772fd4fe7dad","datavalue":{"value":{"amount":"+0.8813587","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936038$C22EF2B7-6A29-461F-B973-DB1A6E5CF1D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76d124f35d10708123e8164f7833aae6d71d5caf","datavalue":{"value":{"entity-type":"item","numeric-id":1082354,"id":"Q1082354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be6b0cb62cecfd74fc87190b768040e0cbfe58e3","datavalue":{"value":{"amount":"+0.8799456","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936038$175F4FBF-59B5-4B94-9BBC-415700F367D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8aa7eebfba991e725642f41fae0c68a678095aab","datavalue":{"value":{"entity-type":"item","numeric-id":4693382,"id":"Q4693382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"122af241accac15baeb1fcc54601c3e7c27bab50","datavalue":{"value":{"amount":"+0.87962055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936038$57C2A63D-B646-4DA3-A578-56C2A120115D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37909bb8245bb3b9ab06a967bb9b877a70d056a3","datavalue":{"value":{"entity-type":"item","numeric-id":3139761,"id":"Q3139761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac3b09da35127bed1763224c79f7a954df916e02","datavalue":{"value":{"amount":"+0.87807685","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936038$FE4B784D-3373-49C6-A346-895A1C98098F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2424f0c4004dc54ce572a0a6a5ad98cbb07b8d43","datavalue":{"value":"A graph be denoted by \\(G=(V,E)\\). From the neighbourhood \\(N(v)\\) in \\(G\\) of \\(v\\in V\\) there follows \\(N[v]=N(v) \\cup\\{v\\}\\). A set \\(I\\subseteq V\\) is called independent if no two vertices of \\(I\\) are adjacent. A graph \\(G\\) is well covered if all maximal independent sets of \\(G\\) have the same cardinality, especially is \\(G Z_m\\)-well-covered if \\(|I_1|\\equiv|I_2|\\pmod m\\) for all maximal independent sets \\(I_1\\) and \\(I_2\\) in \\(V\\). A vertex \\(v\\) is simplicial if it appears in exactly one clique of the graph \\(G\\), and a clique containing at least one such simplicial vertex of \\(G\\) is called a simplex of \\(G\\). \\(G\\) is a called a simplicial graph if every vertex of \\(G\\) is a simplicial vertex or is adjacent to a simplicial vertex of \\(G\\). \\(G\\) is called a chordal graph if every cycle of \\(G\\) of length four or more has a chord, and \\(G\\) is called a circular arc graph if it is the intersection graph of arcs on a circle.NEWLINENEWLINENEWLINEIn present paper \\(Z_m\\)-well-covered graphs are characterized in these three classes by the following four theorems. Theorem 1. If for each \\(g\\in V(G)\\) there is \\(\\ell\\in N\\) such that \\(g\\) belongs to exactly \\((m\\ell+1)\\) simplices, then \\(G\\) is a \\(Z_m\\)-well-covered graph. Theorem 2. If \\(G\\) is a \\(Z_m\\)-well-covered simplicial graph, then for each \\(g\\in V(G)\\) there is \\(\\ell\\in N\\) such that \\(g\\) belongs to exactly \\((m\\ell+1)\\) simplices. Theorem 3. \\(G\\) is a simplicial graph, if \\(G\\) is a chordal \\(Z_m\\)-well-covered graph. Theorem 4. Let \\(G\\) be a circular arc graph that is not complete. Then \\(G\\setminus N[v]\\) is a \\(Z_m\\)-well-covered graph for all \\(v\\in V(G)\\) if and only if \\(G\\) is a \\(Z_m\\)-well-covered graph.NEWLINENEWLINENEWLINEIt is known that the recognition problem of well-covered graphs (and of \\(Z_m\\)-well-covered graphs) in general is Co-NP-complete, but for some classes of graphs it is already polynomial (examples are given in the paper).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936038$FCF7E75C-E9A6-40AA-A97F-43158FB1034F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5936038","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5936038"}}}}}