{"entities":{"Q2713623":{"pageid":2724362,"ns":120,"title":"Item:Q2713623","lastrevid":47617921,"modified":"2026-01-02T05:49:04Z","type":"item","id":"Q2713623","labels":{"en":{"language":"en","value":"Independence and irredundance in \\(k\\)-regular graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1602756"}},"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":"Q2713623$7E3DCA66-D63D-4196-8AF5-E80B4FD30231","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b07679a5a555182392df660b8a02c3ce38267e4b","datavalue":{"value":"0963.05124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713623$EA52005F-8FE8-47A3-8C92-4A7F2F087FF6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d399175a75045d6e68cdfc363866ce63dcafb225","datavalue":{"value":{"time":"+2001-06-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2713623$B9633125-1A73-4405-936B-F71E3A2392A7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713623$1C5FF369-B7B5-4B77-9BCF-DE6055FA63D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713623$CD3271EE-8FB4-45A7-AFC8-3DB7F034EBCA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c46046a86a27c4a88a6ae107508a96382fcc6dc9","datavalue":{"value":"1602756","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713623$2169598B-CE37-4ACD-91E3-3A31F7531640","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2713623$F44C4032-396B-4D88-B56F-EB1F74540010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9833d0f1a4fa9f6bc9851cce376698ce2aedcb9","datavalue":{"value":"irredundant set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2713623$6A5DD515-0931-4387-BECD-D13101D8F06D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2713623$7D15298A-EA8B-4052-B032-579FA72DEB69","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":"Q2713623$14E17D4F-43E6-408E-8584-47A084F56BEA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8aa89cb72bd02f5111f41a72bd591d4d453547cb","datavalue":{"value":{"entity-type":"item","numeric-id":1223689,"id":"Q1223689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2713623$A8EE4F03-DA2B-4B48-BC4E-C7576EDF7803","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c9d1c9ba6bd3f4aa96f0d37d0211dfaad48b281","datavalue":{"value":{"entity-type":"item","numeric-id":251500,"id":"Q251500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2713623$58EE4144-382B-40CB-AC67-F07D1376CD26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"20be73a7a55c4bc82d2a38877aebc7a1d1482e6d","datavalue":{"value":{"entity-type":"item","numeric-id":753846,"id":"Q753846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2713623$9803A9B0-EAE0-49B9-9C36-514C3F6FD960","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f19ef661405f976a68ce060676456c4e7352c4be","datavalue":{"value":{"text":"Independence and irredundance in \\(k\\)-regular graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2713623$8757D445-7162-4EC9-915F-F5499387695F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6f7fbf6651880b9d76c5e78437f7f8284b8f74c4","datavalue":{"value":{"entity-type":"item","numeric-id":6550664,"id":"Q6550664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2713623$07E5A0FE-7F02-4B82-B727-E11BC0D57592","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"be82f0b8a51b96b7c11432f23b45e612093ca4ae","datavalue":{"value":"A subset of the vertex set \\(V(G)\\) of a graph \\(G\\) is independent, if it consists of pairwise non-adjacent vertices. A subset \\(S\\) of \\(V(G)\\) is irredundant, if for each \\(u\\in S\\) there exists a vertex adjacent to \\(u\\) and to no other vertex of \\(S\\). The decision problem INDEPENDENT SET is the problem for a given graph \\(G\\) and a given integer \\(m\\) to decide, whether \\(G\\) has an independent set with at least \\(m\\) vertices. Analogously the problem IRREDUNDANT SET is defined. It is proved that INDEPENDENT SET (or IRREDUNDANT SET) is NP-complete in the class of all \\(k\\)-regular graphs for \\(k \\geq 3\\) (or \\(k \\geq 6\\) respectively).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2713623$01E44D30-207E-412C-A43A-0B294D93707A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9b462d071c33d7d83486f9fef57845bb41d7acf","datavalue":{"value":{"entity-type":"item","numeric-id":190573,"id":"Q190573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2713623$1236E459-677B-47D4-AD65-807DE47F969C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"860d9b8e08c7baec367c7f54b1b8b263696e7c53","datavalue":{"value":{"entity-type":"item","numeric-id":2717906,"id":"Q2717906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"275b29a06266e370b65c027f22dabe5641fd4dbe","datavalue":{"value":{"amount":"+0.8515718579292297","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":"Q2713623$2C50BD7E-ED25-4171-B7A1-257ED15DFD68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"040ec92cc214599ecdf38d6bd02ff3927f501733","datavalue":{"value":{"entity-type":"item","numeric-id":1669583,"id":"Q1669583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"925b5cac5eba9be67ecc80a2b59d843c4aa9f631","datavalue":{"value":{"amount":"+0.8507481217384338","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":"Q2713623$B078C9EA-B7B7-43D0-A4BA-FDFC30E5FF02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"884996bb3c710830ce84622aab27e31355b808c0","datavalue":{"value":{"entity-type":"item","numeric-id":4304413,"id":"Q4304413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4115f97d41be7b7d96f6f7c102cbe88e66d840d3","datavalue":{"value":{"amount":"+0.8484959006309509","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":"Q2713623$B3D32579-6745-4727-8FF9-30C96830F44D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92e84fbd914548fe14a042b1bc5526f4c64bcc29","datavalue":{"value":{"entity-type":"item","numeric-id":709325,"id":"Q709325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4df0e49c77cf6e7fa772ff2b30a68268ed9aa076","datavalue":{"value":{"amount":"+0.8403524160385132","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":"Q2713623$7718A28B-979A-43F3-8BA3-BD4A554DBFB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"042ac2ac6f917530bd4f6893286eab8f815ca238","datavalue":{"value":{"entity-type":"item","numeric-id":3791195,"id":"Q3791195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8783dc957ff54862afcde1847cd60f73421752c1","datavalue":{"value":{"amount":"+0.7953271865844727","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":"Q2713623$63E56E52-094C-489B-B878-80DE9E279BC6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2713623","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2713623"}}}}}