{"entities":{"Q805626":{"pageid":807474,"ns":120,"title":"Item:Q805626","lastrevid":42704209,"modified":"2025-07-08T16:22:35Z","type":"item","id":"Q805626","labels":{"en":{"language":"en","value":"On the existence of (k,\\(\\ell)\\)-kernels in digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4204367"}},"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":"Q805626$FCF66730-28E7-47A2-90A9-537AF3C76ADB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9660eeaa85d0c84ef5429d23747c2c13b03e7d69","datavalue":{"value":{"text":"On the existence of (k,\\(\\ell)\\)-kernels in digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q805626$83B44B41-008B-4BD7-93A7-BCB4ABE0E266","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"413b7c14194af2cd2576325508c05277b2f65c2b","datavalue":{"value":"0729.05020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805626$2B1B2445-A967-45DC-9EBA-A1C9988652D6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9a2aa688e9fbd0b21e6ca23b0c18ca896249313d","datavalue":{"value":"10.1016/0012-365X(90)90167-G","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805626$6374609C-3F25-40FF-9B73-BFDF4A7EC878","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":"Q805626$934C49A4-46A9-4F95-AD95-4E42181DC808","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q805626$3A1313F0-FF13-4972-920D-55D6A7E713F7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"093763a764761b46b7e8df95b26164d771f8c26a","datavalue":{"value":"A kernel in a digraph D is a set of vertices S such that no two vertices of S are joined by an arc and for every vertex \\(x\\not\\in S\\) there exists a vertex \\(s\\in S\\) and an arc from s to x. Let k and \\(\\ell\\) be natural numbers with \\(k\\geq 2\\) and \\(\\ell \\geq 1\\). A set \\(S\\subseteq V(D)\\) is a (k,\\(\\ell)\\)-kernel of the digraph D if:   (1) for each pair of vertices x, \\(x'\\in S\\), the length of a shortest directed path with endvertices x, \\(x'\\) is at least k,    (2) for each \\(v\\not\\in S\\), there exists an \\(x\\in S\\) such that the shortest directed path from x to v is at most \\(\\ell.\\)     Hence a kernel is a (2,1)-kernel. A k-kernel is the same as a (k,k-1)- kernel. The paper presents some results on k-kernels and (k,\\(\\ell)\\)- kernels in digraphs which generalize at theorem by P. Duchet: If every directed cycle of odd length in a digraph D has at least two symmetrical arcs (arcs which are in a directed 2-cycle), then D has a kernel.","type":"string"},"datatype":"string"},"type":"statement","id":"Q805626$F2C7FA57-C57B-40C1-A0AA-CB490E9BD52E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805626$EA7CF278-F6FF-4DEA-A252-C3C8231B5C05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805626$50CFD142-BF18-4BAB-B86C-AD6080B9DD4F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"55a05070a77723911058d11fb1c6580e1b15e56b","datavalue":{"value":"4204367","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805626$ACD988C5-8EBD-442C-8B8B-2DF432D67920","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6502121864a1dff048ddc4823cf928079ab042bc","datavalue":{"value":"kernel","type":"string"},"datatype":"string"},"type":"statement","id":"Q805626$2FC0F87F-2F39-4F20-A04F-B86712D1E5FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q805626$7F9FEB8C-DBA6-4A68-A371-0A207D3650A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49b214501ed6da825da702506d1e3cd3a85b4745","datavalue":{"value":"directed path","type":"string"},"datatype":"string"},"type":"statement","id":"Q805626$18D89724-01D1-4895-B6AC-6E7728C52398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b887ff6a0e36500b18c71f62cea27e0ad61c6ee5","datavalue":{"value":"directed cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q805626$8F38BFC2-C07D-4255-900D-408649289BEF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"422f975a6f5c5687b63af0336205808cd1c581d3","datavalue":{"value":{"entity-type":"item","numeric-id":251511,"id":"Q251511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805626$D33B7365-6FB5-47C0-A6F4-15334AA91D2B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eee744981d92ac19b8d353f3a45a83ebd916fb73","datavalue":{"value":{"entity-type":"item","numeric-id":558237,"id":"Q558237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805626$3C1B9C6B-3098-4B1D-830B-58732397E0EF","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":"Q805626$8B5E1B9B-20CE-41E7-B5BA-F3438B86D9F3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805626$2DA78CB3-DD79-4B5C-AB0F-467256C5B0AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11ad76d3ddfa7a55b034bc9601241a201bd9cb02","datavalue":{"value":{"entity-type":"item","numeric-id":3912817,"id":"Q3912817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805626$EBC2054D-2F53-4C02-8ADA-39A27175A5C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e4f23161b6861f48e678dac651044d3d8ea78a3","datavalue":{"value":{"entity-type":"item","numeric-id":4748178,"id":"Q4748178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805626$804B2945-8EED-47A8-BF61-16398E65DF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9153fae7945081d0821c3aed74529ec0cec94a5","datavalue":{"value":{"entity-type":"item","numeric-id":4745842,"id":"Q4745842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805626$CDEA4CC7-B6B2-4AFD-82F6-B516F142AF2B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"806671e17ba63f8308565fbae47aaf4dbbe6cc38","datavalue":{"value":{"entity-type":"item","numeric-id":547555,"id":"Q547555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51c1f7a27c6d755236a6263488f63bf9ee7055ec","datavalue":{"value":{"amount":"+0.96248025","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":"Q805626$E03B4105-C34E-47C3-866F-CE7BD514EABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"024f40e912d896a61d82840f4d07418df07c7d86","datavalue":{"value":{"entity-type":"item","numeric-id":4254303,"id":"Q4254303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2e3a4712da4ec3136b78eefe6096c2d072bb446","datavalue":{"value":{"amount":"+0.95161927","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":"Q805626$E7DBA26C-72A9-4A3F-9A53-C37FB06134FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40a55947f85fdcda7e6aacc60f5cca9518bf59a8","datavalue":{"value":{"entity-type":"item","numeric-id":2443409,"id":"Q2443409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"591989ccdbe3f661b0e36baf8a8da87dcde2de9f","datavalue":{"value":{"amount":"+0.9443906","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":"Q805626$52BE5E5C-D049-4241-94A5-33907FEC241E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35b48d6a8e315bc77f8d3b81f3953c7b2e701c7c","datavalue":{"value":{"entity-type":"item","numeric-id":2509534,"id":"Q2509534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf5653a6a3dc4588ff17b62b17ed3c7a61daccf2","datavalue":{"value":{"amount":"+0.94228506","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":"Q805626$253DEB9D-BD95-4108-A648-038732CE1494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9ba2de1ea412bc0135def4408281a83f3e252e8","datavalue":{"value":{"entity-type":"item","numeric-id":3534483,"id":"Q3534483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"713f0dc1ba17a906a7567b691746f131c1a26ff5","datavalue":{"value":{"amount":"+0.9383171","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":"Q805626$BF777C74-C8A4-42B4-9090-0E1EF9BB5DA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce76576bbe189567d239f5900331c20f676dd24c","datavalue":{"value":{"entity-type":"item","numeric-id":5324102,"id":"Q5324102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"295768795c15b550e97e81ac0adbfece257e4c67","datavalue":{"value":{"amount":"+0.9269803","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":"Q805626$F630670F-31EC-4C85-AD3C-2214D54421B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1deb7f0553a88d618fccb0885aff5facd639f35c","datavalue":{"value":{"entity-type":"item","numeric-id":3504799,"id":"Q3504799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65f6457a7792b6336016b14a5f1a05dd7b0a23db","datavalue":{"value":{"amount":"+0.92537737","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":"Q805626$4C612FA5-5618-4A7A-A60B-33B285F94D3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbfc971389332e9a99baf40c830ba926fcc49554","datavalue":{"value":{"entity-type":"item","numeric-id":1025568,"id":"Q1025568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18a9c4135be892d03ad82287fa79aecbf7218f1c","datavalue":{"value":{"amount":"+0.9250482","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":"Q805626$7138514C-D23F-46D1-A24E-410CBE033B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57a5a0ff440c6019d9a377f5ff40c2c96e3b6bf6","datavalue":{"value":{"entity-type":"item","numeric-id":2822834,"id":"Q2822834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b005473e576d4987d881366fcb1bd6cd99e57ba5","datavalue":{"value":{"amount":"+0.92334574","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":"Q805626$2AA6EF69-2165-4D58-B054-94FAE5B3BE10","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":"0edf1ede044626eab76641767d1bf6b2bd39a3f5","datavalue":{"value":{"amount":"+0.9225172","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":"Q805626$245BC3EE-F41E-499F-824C-6A957020ECF5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:805626","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:805626"}}}}}