{"entities":{"Q907223":{"pageid":909071,"ns":120,"title":"Item:Q907223","lastrevid":65256402,"modified":"2026-04-12T01:20:48Z","type":"item","id":"Q907223","labels":{"en":{"language":"en","value":"Semi-degree threshold for anti-directed Hamiltonian cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6534965"}},"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":"Q907223$911729A7-7623-4345-954B-4257EB13BE28","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4852f8d47659f508faad943b3f11bd5806676273","datavalue":{"value":{"text":"Semi-degree threshold for anti-directed Hamiltonian cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q907223$9B64F599-247F-46CE-9F58-D337B8447C97","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8605a5dfffbe978d2071c4ad3476736688610f20","datavalue":{"value":"1329.05127","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907223$2646241F-09CE-4B56-896A-0938DCBC0C58","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"66e93ba842431edddbc94363cb268107b217dcf0","datavalue":{"value":{"entity-type":"item","numeric-id":281606,"id":"Q281606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$37F79128-BEA8-4208-9305-0B1BDBF0D8DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f988a0b91db170aa38adba2cb9825a10a2dfd1a7","datavalue":{"value":{"entity-type":"item","numeric-id":345112,"id":"Q345112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$6E54FD5B-5AA6-4850-A5BD-40A22A0708D7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$3B6CD8D2-2D0D-444D-80D8-62B3CB3D5FBB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e3f0504cdbec36416c8068369865aa5a0a508332","datavalue":{"value":{"time":"+2016-01-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q907223$E5491478-3714-4D3C-8CC5-A78BA9A8B981","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"101f0b441f4f8879d0cabfdd285e4901e1bb2550","datavalue":{"value":"https://arxiv.org/abs/1308.0269","type":"string"},"datatype":"url"},"type":"statement","id":"Q907223$06B40A34-2E9F-470B-BE8A-436470A8CAC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"c4c3cf57dd925ef92a9d193ff8862bbe68187950","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p34","type":"string"},"datatype":"url"},"type":"statement","id":"Q907223$5FDDCE40-FA30-4FFE-8290-23D39B15E3CC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c8d235dba33bc5a0d759f863698a4c67b8d81e7d","datavalue":{"value":"Summary: In [C. R. Acad. Sci., Paris 251, 495--497 (1960; Zbl 0091.37503)] \\textit{A. Ghouila-Houri} extended Dirac's theorem to directed graphs by proving that if \\(D\\) is a directed graph on \\(n\\) vertices with minimum out-degree and in-degree at least \\(n/2\\), then \\(D\\) contains a directed Hamiltonian cycle. For directed graphs one may ask for other orientations of a Hamiltonian cycle and in [Ars Comb. 10, 205--209 (1980; Zbl 0448.05034)] \\textit{D. D. Grant} initiated the problem of determining minimum degree conditions for a directed graph \\(D\\) to contain an anti-directed Hamiltonian cycle (an orientation in which consecutive edges alternate direction). We prove that for sufficiently large even \\(n\\), if \\(D\\) is a directed graph on \\(n\\) vertices with minimum out-degree and in-degree at least \\(\\frac{n}{2}+1\\), then \\(D\\) contains an anti-directed Hamiltonian cycle. In fact, we prove the stronger result that \\(\\frac{n}{2}\\) is sufficient unless \\(D\\) is one of two counterexamples. This result is sharp.","type":"string"},"datatype":"string"},"type":"statement","id":"Q907223$C87E2BFF-BA51-43D8-ADFA-00BF899D9392","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907223$9489D592-A5FD-41D5-82EB-73615602CDA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907223$649FF587-F287-44A3-9A99-A64437F43D38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907223$42B801ED-D138-47E4-8787-04F90818897E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907223$D7CE7CED-62CE-414D-9704-750A06048783","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f168a40484fdba161e9270d06138aff182d226d5","datavalue":{"value":"6534965","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907223$D953B72B-4613-4D9F-9066-7AE031AB2FB4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q907223$2390A325-7F9F-479F-8B01-3D5D918BCB6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"862b3f9bd3562fb19afcb46cb40fc8fc3f64ed24","datavalue":{"value":"Hamiltonian cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q907223$3E92DE45-FE96-4D8C-8752-E7A010D1DC7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4b98b5353082f5ae3dd3eedbb2c57d8903e4ca5","datavalue":{"value":"directed graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q907223$87F48EAE-1C3E-42DB-8762-C657BC552C3E","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":"Q907223$FF44CC60-9034-4312-B45C-44911434FD16","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"62cd074a052aad5872b02556289f682d7f2c9a0b","datavalue":{"value":{"entity-type":"item","numeric-id":2376100,"id":"Q2376100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$EF5A2431-4531-41D7-A4B8-4FF929F39577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1becd5b241a85b39ee51b84a0be277279c850579","datavalue":{"value":{"entity-type":"item","numeric-id":1172647,"id":"Q1172647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$F6ED73B9-F661-4696-BB43-B3E6DB6496AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$E0CA49B0-9987-4536-B7F3-4B948691CCB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bd8325ec675c8ff148c76ffd938315ae401c50f","datavalue":{"value":{"entity-type":"item","numeric-id":1850018,"id":"Q1850018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$FFF4208B-829F-4A68-968B-AFDA0DDCEA70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62e967816953cecad41268e715794a55d56323d","datavalue":{"value":{"entity-type":"item","numeric-id":3577833,"id":"Q3577833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$F5FFB7BD-A842-474D-8B15-13D80D40F0D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3159cfa27d8998a0889650e457a61616bca97f34","datavalue":{"value":{"entity-type":"item","numeric-id":5812733,"id":"Q5812733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$919E003C-3DCA-4FD5-9BBD-E266B6BAFB1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33aee81de05b2e5a7272794b15bf6407d9521aee","datavalue":{"value":{"entity-type":"item","numeric-id":409370,"id":"Q409370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$FB1A6FD8-C427-4B33-A401-650644E965F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"770841483c24d9410a5dde804415d5f3ae756334","datavalue":{"value":{"entity-type":"item","numeric-id":3266934,"id":"Q3266934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$CA4626B1-B454-43DB-ADD3-CD7383EA5797","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36acf7163043c5d33d832687769e06742e60f66e","datavalue":{"value":{"entity-type":"item","numeric-id":3893955,"id":"Q3893955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$1D44A6FC-A021-49DB-90E0-A9B8DFDF0DEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cc8ea00ddb6f08950d29b3c36336a8d30ff257e","datavalue":{"value":{"entity-type":"item","numeric-id":4842703,"id":"Q4842703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$2CC74C1A-2A1C-4798-B540-017F022E7275","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb092ee573da95ee892914fa47f0b610a8132b04","datavalue":{"value":{"entity-type":"item","numeric-id":4347899,"id":"Q4347899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$D9E36A7B-F8F2-4571-A903-DD77602E2FF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87a71d5846acdc083260c22516228c02757735f1","datavalue":{"value":{"entity-type":"item","numeric-id":960978,"id":"Q960978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$6729F1D3-4ABB-4E93-A71F-918586232509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$9066D824-9157-47E2-93C3-DE43F6535438","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"437ebe0c1320329dc48bb92b41d79db15821185e","datavalue":{"value":{"entity-type":"item","numeric-id":2626464,"id":"Q2626464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$6CFEE0F0-4BA9-4405-B9B3-C57021A80B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"473cd81f193b507bb3ef997e12cb483d7a4e87d7","datavalue":{"value":{"entity-type":"item","numeric-id":2380274,"id":"Q2380274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$829448F0-0072-435D-A747-A4076617C548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d6543025660bd193351c3633841b97b857c084a","datavalue":{"value":{"entity-type":"item","numeric-id":2553373,"id":"Q2553373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907223$0E4A368B-7008-4882-A444-5205E909CCBA","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"079a9611ed41bde2a48154f69c916e3f11f0b85a","datavalue":{"value":"bafkreifcrev4jhmdltgyyomycxvwxnn46wtvc3vbp3ddzdowij3vbvxdp4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907223$0CD639B3-75D5-4C46-9D9C-D6CA3AFAD084","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd873a4788cfc4b95307151a6bd0cab08f2f2f68","datavalue":{"value":{"entity-type":"item","numeric-id":2376100,"id":"Q2376100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02f434b70dc725d7d0222dc45bd7b942d28b8264","datavalue":{"value":{"amount":"+0.904594659805298","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":"Q907223$BAED45FC-32A3-4A60-9B05-B330C0A21717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33bc753df13f845fa76129221934f96e65d14f9e","datavalue":{"value":{"entity-type":"item","numeric-id":2380274,"id":"Q2380274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7c21ea12bd5ead4cfb08e2bf99058ebdf14d9c2","datavalue":{"value":{"amount":"+0.8743834495544434","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":"Q907223$089A9DFA-924E-47E9-B5D3-C9AD61E73E2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0aaf2c0e792fff7b8cbb68b16d80aeedf6fa3d06","datavalue":{"value":{"entity-type":"item","numeric-id":3165993,"id":"Q3165993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be1b122913ab547858fb43972cdc1180d1c8d64f","datavalue":{"value":{"amount":"+0.8670481443405151","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":"Q907223$5093E013-4732-4E14-9E50-92F018FC3309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17078f0b48adf1a6da3cf2072aec16705062d872","datavalue":{"value":{"entity-type":"item","numeric-id":2944460,"id":"Q2944460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46d5321ca7affbfb767dec5f0e6cc9cb0d037f7d","datavalue":{"value":{"amount":"+0.8373588919639587","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":"Q907223$4EA078BA-D8A9-47DB-979C-560B39B529B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e76fb0fd3a4f9a129a3812cca286ab521ce69dd","datavalue":{"value":{"entity-type":"item","numeric-id":409370,"id":"Q409370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"243a77964f03c0a4e5aecc9d854a72866c808ac5","datavalue":{"value":{"amount":"+0.813854992389679","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":"Q907223$86CB7D96-F9C0-45EA-B287-F2C2F9549F7D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Semi-degree threshold for anti-directed Hamiltonian cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Semi-degree_threshold_for_anti-directed_Hamiltonian_cycles"}}}}}