{"entities":{"Q1939576":{"pageid":1950318,"ns":120,"title":"Item:Q1939576","lastrevid":78124652,"modified":"2026-05-06T10:50:37Z","type":"item","id":"Q1939576","labels":{"en":{"language":"en","value":"On the structure of the minimum critical independent set of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6141133"}},"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":"Q1939576$FB854CA5-E060-4600-90CA-DB9B1D4358F9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"61f671b4e617e21675867165093b9f4ca9ddea49","datavalue":{"value":{"text":"On the structure of the minimum critical independent set of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1939576$0E24B70F-6C44-4DB1-B71E-9038B2905FCE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"36194bb027d8f154347067bcc9fb0f2e9ad86e29","datavalue":{"value":"1262.05088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1939576$DC0DEC17-9C9D-4462-8990-5145093593D2","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":"Q1939576$6021FD09-10DC-44B4-9FBC-292DDA771735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f8a20409ab1b7a302e9e39ef4598e89538b5cf5","datavalue":{"value":{"entity-type":"item","numeric-id":328719,"id":"Q328719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1939576$18F7B3EA-8F16-446F-9083-F089588F5D7F","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":"Q1939576$EF894F1C-740E-4B31-A939-510A22C3D992","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"32836873df0c40f57cb1a44db33702027712a230","datavalue":{"value":{"time":"+2013-03-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":"Q1939576$5906917E-AF10-4933-8682-3C152879F64A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c09516652cdecaf2e4c956e5d5db3414a559c21a","datavalue":{"value":"https://arxiv.org/abs/1102.1859","type":"string"},"datatype":"url"},"type":"statement","id":"Q1939576$19AE2FBE-DFA8-44CB-A2EC-9F34C329D442","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d367e413cbb8acfad1d64513d4ac27ab49b948da","datavalue":{"value":"A subset of vertices \\(S\\) of a graph \\(G=(V,E)\\) is independent if no two vertices of \\(S\\) are adjacent. An independent set is critical, if the difference between its cardinality and the cardinality of its neighborhood is maximal over all independent sets of the graph. The core of \\(G\\) is defined to be the intersection of all maximum independent sets of \\(G\\), while \\(\\ker(G)\\) denotes the intersection of all critical independent sets of \\(G\\). Previously [SIAM J. Discrete Math. 26, No. 1, 399--403 (2012; Zbl 1246.05122)] the authors showed that the kernel of \\(G\\) is a subset of its core. In the paper under review the authors present several structural properties of the kernel. In particular it is shown that the kernel is the union of inclusion minimal independent sets with positive difference number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1939576$8C5EF6C3-AE96-407B-BDEA-40655F9F0154","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"489b50af879f20c258267402ff7bb6342fefbc88","datavalue":{"value":{"entity-type":"item","numeric-id":588147,"id":"Q588147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1939576$EC4EBE0D-20BC-459C-97CF-1CF4C70E831E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1939576$E60BA105-95BB-4500-ABD6-67B93BE2B4EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1939576$8E2E2EC5-0EC7-4288-BD2D-7025B6B89B84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1939576$AA1EC3DD-FC9A-41BA-85D6-5E4658663163","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0a03ee0bd33c9bba8cb04ee61ba9d05c039ae1aa","datavalue":{"value":"6141133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1939576$EE2DEEF3-3B84-471A-9E95-FA6573DAE9FA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1939576$A7BDAF4C-8D76-4FD1-AB33-8403BEB312A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d429947695a58848653d815a4887e71963248f3e","datavalue":{"value":"critical set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1939576$4E17A189-45A2-4014-9E94-9F98989C7922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6502121864a1dff048ddc4823cf928079ab042bc","datavalue":{"value":"kernel","type":"string"},"datatype":"string"},"type":"statement","id":"Q1939576$E2450935-C611-4A75-BA7A-710A326E8A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"274d092672a414a51cbf1f9c6392a720be1e7927","datavalue":{"value":"core","type":"string"},"datatype":"string"},"type":"statement","id":"Q1939576$008845EA-482E-4EDB-9DDC-B2D4DF044A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1939576$42E97D12-A886-4222-B7FB-5C077EE3380B","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":"Q1939576$35543421-A0E2-439C-89EA-A341BC72A6D4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5bbcca47b543c02bece94e944aca14b8753033c9","datavalue":{"value":"W1637433852","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1939576$048E66DC-8275-458C-B10F-C8646993A670","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3c8940c610d634fbabc86e6513de86c534bd0635","datavalue":{"value":"10.1016/J.DISC.2012.12.008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1939576$2188EA9B-1FDC-42B5-9950-CB97AC9E49CE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c46d9a80dca1199976b3e06946e04c66a5ffa21","datavalue":{"value":{"entity-type":"item","numeric-id":2902909,"id":"Q2902909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbaff384f1432e3e79dcdf980eb1805a8aa43cd2","datavalue":{"value":{"amount":"+0.8948239684104919","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":"Q1939576$B65D9E05-4BC0-4B33-9C56-9159BBCDF6EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d850cc6932cffc9f7dd934b1a4d41852daf4109","datavalue":{"value":{"entity-type":"item","numeric-id":2181736,"id":"Q2181736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16afb933e56635c485c60fb646c075b930dc4031","datavalue":{"value":{"amount":"+0.874722421169281","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":"Q1939576$B7645D75-7B1F-443A-8A63-400D746936EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9dd2461b6e8e78f3bd54f553e87d5fca8ae9a54","datavalue":{"value":{"entity-type":"item","numeric-id":368442,"id":"Q368442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f5bb9beeac80f097146bd59e95dc143d4b5ce0f","datavalue":{"value":{"amount":"+0.8234190344810486","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":"Q1939576$27EE4EB5-2CA9-4FC6-B60F-8F717902431B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8269b455aab61c364fbd31b11aa924c8b054bd90","datavalue":{"value":{"entity-type":"item","numeric-id":2146733,"id":"Q2146733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed5bbcf6b2c8bb3ef7de2bd101ee75a84bb2b27f","datavalue":{"value":{"amount":"+0.8062806725502014","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":"Q1939576$BDA9DC2D-CEB6-4611-8BC0-EC4648C638BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bdbdba4bf08259c56f43019157ccb92309f1550","datavalue":{"value":{"entity-type":"item","numeric-id":2629485,"id":"Q2629485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2b9631362cb7ef02d4019d1cb2a5788ce759f81","datavalue":{"value":{"amount":"+0.8045862913131714","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":"Q1939576$3465A441-4628-4A88-BA84-0D3242A623AF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the structure of the minimum critical independent set of a graph","badges":[]}}}}}