{"entities":{"Q1084409":{"pageid":1095161,"ns":120,"title":"Item:Q1084409","lastrevid":48998830,"modified":"2026-01-06T11:11:33Z","type":"item","id":"Q1084409","labels":{"en":{"language":"en","value":"Even cycles in directed graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3979097"}},"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":"Q1084409$0710D8BC-58E3-48E3-BADB-7B48CB56279B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d3bd9b82b024e1c732a493ec233b78344a0eab6e","datavalue":{"value":{"text":"Even cycles in directed graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1084409$D6190781-48AA-423D-AD77-0BE2A520CC7B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d93833e9f3ccc7d2cbce2a3b82bd251a1dc98d04","datavalue":{"value":"0606.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084409$3477B2C6-B7C0-44CB-8FDB-C60A3705A381","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d3bc09a684bf43e172bcc9974547476ad1875aed","datavalue":{"value":"10.1016/S0195-6698(85)80025-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084409$A387CC4F-0D95-4973-86BF-59FFE77B7491","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aec857263cee52fe850f36c12f5157e5c8f0a013","datavalue":{"value":{"entity-type":"item","numeric-id":228790,"id":"Q228790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$87F027D0-D41F-41E5-B6CA-2810409CE438","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$3BB55D8B-6BBD-4216-BF78-BC68015282DE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1084409$1E081F5D-9E0E-4344-845C-9103D37C8159","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"10c68258b55f7f5014f9b49a3d06f909bef88449","datavalue":{"value":"In this article the author shows that given an edge e in a digraph G it is NP-complete to decide if D has an odd cycle through e and it is NP- complete to decide if D has an even cycle through e. Contiuing his investigation of even cycles in digraphs, he shows that for every natural number k, there exists a digraph \\(D_ k\\) with no even cycle such that every vertex of \\(D_ k\\) has outdegree k (settling problems of Lovasz and Seymour). Furthermore, he proves that a digraph of order n and minimum outdegree \\([\\log_ 2n]+1\\) contains, for each edge set E, a cycle containing an even number of edges of E, and this bound is best possible.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084409$6146BCE9-944A-4D50-9872-E670893FE22F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084409$1D24701B-EEB7-4A14-A38F-63E1CF2AE3FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084409$DCA722E0-3AE8-44D7-8744-F806DF8BA3DC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f47d94f1865282dd72d514de4c963c3b563a0122","datavalue":{"value":"3979097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084409$FCB5D9D9-918C-476E-9494-EB23685B7F5F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e2084cc29e670eea4c95dc6235db08eceb1eb8c","datavalue":{"value":"NP completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084409$FDF68259-6C95-4BF7-BA1C-75A4937A9CF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf7c8c6f6597b6191535a25cf080e76f22bc080b","datavalue":{"value":"even cycles in digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084409$11FD0431-D061-408D-945C-FA7F9CC079D8","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":"Q1084409$BF8792A7-5B2E-4423-8441-CFD062A55C60","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff61fd0b129f826f2212a187aba22998ab2225e7","datavalue":{"value":{"entity-type":"item","numeric-id":5603090,"id":"Q5603090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$C40D5421-C01B-4F16-A519-F48B92602CAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b3d018f710168a4c0bbc22dd78d95193c542bca","datavalue":{"value":{"entity-type":"item","numeric-id":3907591,"id":"Q3907591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$BB500201-4F8E-4814-A5E1-8101639AED27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$ED4F5F9A-2330-4C1E-95A1-8B9964FDAEA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2045a7ec56e01f15e3eae4db248ef2b73a81db","datavalue":{"value":{"entity-type":"item","numeric-id":1132111,"id":"Q1132111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$456CA953-1EE0-4A50-8E3A-F1097ACD12CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cada4cdf0307329442151573a609046b068fa91","datavalue":{"value":{"entity-type":"item","numeric-id":1158436,"id":"Q1158436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$712CAC48-A78A-4695-8948-E13283AF7713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2508b233692c7793ff0069d74568d019767dfeea","datavalue":{"value":{"entity-type":"item","numeric-id":5515142,"id":"Q5515142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$14A68580-A63F-4328-9FF5-6099D033AF21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0573438df5c42b6311f4ef8a1122e32922dc39b","datavalue":{"value":{"entity-type":"item","numeric-id":2535846,"id":"Q2535846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$1B7F990A-5597-4F7E-928E-B7567AE6D54D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa5434d99603b4edd569d7d07b4e9980a4940032","datavalue":{"value":{"entity-type":"item","numeric-id":795898,"id":"Q795898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$3EDC45EB-59BE-4214-8E37-891ADA41EDA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71c436b285ab314532a3578cdb7a96311b0e09ce","datavalue":{"value":{"entity-type":"item","numeric-id":5600748,"id":"Q5600748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$F7FAE051-5EC8-43FB-BE7F-A1D4390E5448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ac6085efda3fa1153d7f93f6374d3b4ce8ea91a","datavalue":{"value":{"entity-type":"item","numeric-id":4075398,"id":"Q4075398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$5C219827-A47C-418C-A32C-1ED9ABCD7141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49245e0aa29f3d0b8a4f3aa138d592837bd9a7fb","datavalue":{"value":{"entity-type":"item","numeric-id":4083461,"id":"Q4083461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$E5075EE3-B3E1-4980-A00A-4A3AF9F6C2BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0de6f029d1f45e2c80d48c6afeeca125f95a3db9","datavalue":{"value":{"entity-type":"item","numeric-id":2531599,"id":"Q2531599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$1EE0512D-C9DC-4BC3-88BB-C26BCD8FAE9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c2a94903479e9aeb3692183810e4827037bf66f","datavalue":{"value":{"entity-type":"item","numeric-id":2555085,"id":"Q2555085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$DA369727-0351-454A-8FCD-FA627AEEFF5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"245abb3a90f1500c3f27160e6c2ee2204c5ca560","datavalue":{"value":{"entity-type":"item","numeric-id":4053703,"id":"Q4053703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$B13C7FEC-7267-4605-8770-70A752409B6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3aa94081ff408739b9511529c04a8484d726767e","datavalue":{"value":{"entity-type":"item","numeric-id":3661617,"id":"Q3661617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084409$D7E71617-3C7C-4BC2-B18D-F37EB44F8BE2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2358276172cd3ce80c203af7e3ab53668ed7fe4b","datavalue":{"value":{"entity-type":"item","numeric-id":3993798,"id":"Q3993798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"907893c975bc1b198aad76a0044f270066778245","datavalue":{"value":{"amount":"+0.8560194969177246","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":"Q1084409$7EAAC9EA-E0E0-4A6C-B842-87C4953329D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df777b9623fdd9fa30bd3e10641a7fff3be3a88d","datavalue":{"value":{"entity-type":"item","numeric-id":1093650,"id":"Q1093650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51777b14a05bf9cf0e5ba68bbdcb8bdce27f35fa","datavalue":{"value":{"amount":"+0.8551452159881592","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":"Q1084409$03D3BA78-0616-460C-AD4B-E6978EE93535","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a1c6b9fea3e9a043df0d08907d3da1180566ca6","datavalue":{"value":{"entity-type":"item","numeric-id":4209272,"id":"Q4209272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3aef2f0355a9fb6fe4f1627cf9de54b5d8189aab","datavalue":{"value":{"amount":"+0.8507492542266846","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":"Q1084409$423C7EE4-5FA8-41FE-ADAF-AFE2EEAC838B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b60e5f4445d2acf3bbfbb45ea7a5f9299cab649","datavalue":{"value":{"entity-type":"item","numeric-id":4307053,"id":"Q4307053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71f95ace942c7c58cb2f0db5254afaca07703804","datavalue":{"value":{"amount":"+0.8405956029891968","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":"Q1084409$C003DF4C-613A-4B56-B1C5-D9C1A6F92A56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd3b4e1a529879cc603890c21902b38c94bf3b9c","datavalue":{"value":{"entity-type":"item","numeric-id":5935601,"id":"Q5935601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a78d08daada977839519da51bf0f196f52ff9476","datavalue":{"value":{"amount":"+0.8395110368728638","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":"Q1084409$30DA513F-2C42-4AE7-979B-871BA6D501E6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1084409","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1084409"}}}}}