{"entities":{"Q1923523":{"pageid":1934265,"ns":120,"title":"Item:Q1923523","lastrevid":82048670,"modified":"2026-05-06T19:58:49Z","type":"item","id":"Q1923523","labels":{"en":{"language":"en","value":"Kernels in graphs with a clique-cutset"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 932565"}},"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":"Q1923523$84A31E4D-5D1C-4AA6-AE8D-E9F2B1A440B6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"78b28bed90d4373a72beb2aeb51e9b3e33b91076","datavalue":{"value":{"text":"Kernels in graphs with a clique-cutset","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1923523$26BD226C-073A-4B80-8FB6-D5E71D41AD6F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"19e6d58eca0d47e8ca8f7a31331b60e2c6b3095e","datavalue":{"value":"0856.05083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923523$3F73B08F-1604-4E40-B855-CE307075B6F6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"11974e203cda6b6fff0c9e3f1e9b57cd1e6645c7","datavalue":{"value":"10.1016/0012-365X(96)00018-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923523$4C241DD4-B65E-45A2-A049-BC0FBDF7A6DA","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":"Q1923523$F69ACEDF-7FD0-44BE-A50C-393D94877960","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ea5fab42a47e0498fcbbd07caa78104b7cdcbf02","datavalue":{"value":{"time":"+1996-10-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1923523$2AB9EFBB-4028-4B5A-B233-3B4D9ADA463A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"305fe30bb27a0256c409007ca65b7f4c5b3783cb","datavalue":{"value":"Let \\(G\\) be a finite directed graph without multiple arcs or loops. A kernel of \\(G\\) is a subset \\(K\\) of vertices with the following properties: (1) every vertex of \\(G - K\\) has a successor in \\(K\\), and (2) there is no arc between any two vertices of \\(K\\).   Not every \\(G\\) admits a kernel, but many conditions are known that imply the existence of a kernel. \\(G\\) is called kernel-perfect if every induced subgraph has a kernel. To investigate what kind of graph constructions preserve kernel-perfectness, the concept of clique-cutset is introduced. A clique-cutset \\(C\\) is a subset of vertices such that \\(C\\) is a clique and \\(G - C\\) is disconnected. For every connected component \\(A\\) of \\(G - C\\), the subgraph induced by \\(A \\cup C\\) is called a piece of \\(G\\) with respect to \\(C\\). The author obtains the following result: Let \\(G\\) be a directed graph which admits a clique-cutset \\(C\\). Then \\(G\\) is kernel-perfect iff every piece of \\(G\\) with respect to \\(C\\) is kernel-perfect (Theorem 1).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923523$549667E7-8E6F-44D2-BFE9-D5F2F8DB7133","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923523$DDB01A54-D980-4A5E-938C-40F47CCC2673","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"123c8816847d7ddff570e646dd30b25fab25d8f9","datavalue":{"value":"932565","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923523$D77DDE90-D045-474E-B4FE-EAC9F7FD14F5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6618ab5a9ff8f4223ffbce869a4a5b78a75cc1f0","datavalue":{"value":"kernel-perfect","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923523$8A869625-409D-46EC-9BE9-AC830A685C7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5741de6de3bb0707fbad30952eb66d1dde60560e","datavalue":{"value":"clique-cutset","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923523$F248A348-1A27-4610-9D2D-99D265D362B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fa4b2bd7acec487832f9dc720d3f9ab0ccca26a","datavalue":{"value":"piece","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923523$FF1F2666-BFAA-4786-A14B-40CCFABB408A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf023653318cc5b8c727563611596d2cf1a818a","datavalue":{"value":"directed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923523$BE9838EC-5721-471D-BA7F-1E753608003F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9cafd1c5926e63e5f13473d806059c3563030bbc","datavalue":{"value":{"entity-type":"item","numeric-id":1301843,"id":"Q1301843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923523$92840C3A-DCF3-44C9-90C3-69A82DA392C0","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":"Q1923523$A6893827-E3FA-460F-8915-70046BB2AD39","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":"Q1923523$BD7B86A1-2A77-4A1D-BA4A-F1ED8ED4BA8E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09b06ada4a02303c79d7ffc00581d47956a243d6","datavalue":{"value":{"entity-type":"item","numeric-id":4099676,"id":"Q4099676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923523$0B91280A-FBD2-4355-8891-E0D314B87509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8922b884252f5daff66373222fbaf1cb25a2899","datavalue":{"value":{"entity-type":"item","numeric-id":5596082,"id":"Q5596082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923523$2FCE8B43-4A6B-4CC8-BCFC-1EC98E3D5BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"571289e7c516224687771a058d92473901f168e0","datavalue":{"value":{"entity-type":"item","numeric-id":1168729,"id":"Q1168729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923523$0B04F4D2-7CC1-4C5F-888F-FCA8BF957C7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a19916b6182f29d75727ad3b196374d3048e88a","datavalue":{"value":{"entity-type":"item","numeric-id":908943,"id":"Q908943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923523$1B136470-072D-438F-B021-AD4C0EE24707","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7b4415362f738a31b3977642531c2f4640b69a9","datavalue":{"value":{"entity-type":"item","numeric-id":3703918,"id":"Q3703918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc1cf77d144551246bace101909e5c001fddc785","datavalue":{"value":{"amount":"+0.9051385","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1923523$E4AA4E76-D32F-4548-81CF-08B5AF6FF466","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b85f8701854deebae7cef3005979dbe6247bfac","datavalue":{"value":{"entity-type":"item","numeric-id":5048305,"id":"Q5048305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"991bf8383d2a870e011322ebf58513930c3049bf","datavalue":{"value":{"amount":"+0.90366083","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1923523$1FF4B247-C952-422B-A111-724EE0503840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18df697945cdb0a41af323dd23aae7c138014766","datavalue":{"value":{"entity-type":"item","numeric-id":5874537,"id":"Q5874537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"991bf8383d2a870e011322ebf58513930c3049bf","datavalue":{"value":{"amount":"+0.90366083","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1923523$75B64DD3-63A4-4600-8657-AAC381279872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"763753aef68cc26db1dfb64ccb4a93179101dd1d","datavalue":{"value":{"entity-type":"item","numeric-id":516902,"id":"Q516902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95d9bb0bb1ac8b89e5255be683e91fb6cb7e6b0d","datavalue":{"value":{"amount":"+0.900379","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1923523$CDA627A7-6C94-4E46-B2C5-8A3F8A9D8476","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61053d319e285380d99a184d6dfa5dc723f103c2","datavalue":{"value":{"entity-type":"item","numeric-id":1821791,"id":"Q1821791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0770656a40ef6d71f5057865c697e76b5d20881e","datavalue":{"value":{"amount":"+0.899423","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1923523$3686B076-2DAE-4279-AADD-1EAD68A5A040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"323be96e47dfb325ee744173b16b063e5ade9fad","datavalue":{"value":{"entity-type":"item","numeric-id":1377857,"id":"Q1377857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c03f86faac3718df95b1cfd9241dc46aa4e245b2","datavalue":{"value":{"amount":"+0.89889276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1923523$0C0D06A5-03D0-44E1-B080-51D213DB6F62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84be86dbcae501db682aab2b2848ea7c35d7c47b","datavalue":{"value":{"entity-type":"item","numeric-id":5135789,"id":"Q5135789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dd67626c0589cb005943d1fc9ff76209534b6ba","datavalue":{"value":{"amount":"+0.89346826","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1923523$B4F05D00-D6EE-4912-9721-9F5956A482EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7e26151568c9ce6bf4cf7f55be80959ef2a6a56","datavalue":{"value":{"entity-type":"item","numeric-id":2454043,"id":"Q2454043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"552c6adf67bf488035c2b42fc933c8200092c191","datavalue":{"value":{"amount":"+0.8929303","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1923523$2A3DFC58-A580-4392-8A54-65FFBC58FA47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2741df99f9db341a170b4b972307e8a62fcc28c2","datavalue":{"value":{"entity-type":"item","numeric-id":684411,"id":"Q684411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c010329f61dd6f1cc361ade64059fe707416cc47","datavalue":{"value":{"amount":"+0.8922317","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1923523$E58BB6BF-EA56-4BFB-A0D7-DB276B062436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0e414fe191467f4666700101f8e954a148ab550","datavalue":{"value":{"entity-type":"item","numeric-id":2413155,"id":"Q2413155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c712632de68360fe5954075b55971d1131602306","datavalue":{"value":{"amount":"+0.8912479","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1923523$24841253-0433-480F-9CF2-73B96E4E6953","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Kernels in graphs with a clique-cutset","badges":[]}}}}}