{"entities":{"Q396945":{"pageid":398712,"ns":120,"title":"Item:Q396945","lastrevid":52065845,"modified":"2026-01-20T21:06:07Z","type":"item","id":"Q396945","labels":{"en":{"language":"en","value":"Computational results on the traceability of oriented graphs of small order"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6330354"}},"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":"Q396945$A7A2758C-E4FB-403B-B506-EE863127D3BC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"79aa234e20c34e698df3cd3e339a04fd654a66cf","datavalue":{"value":{"text":"Computational results on the traceability of oriented graphs of small order","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q396945$D1A7A754-2EB8-4D78-96D6-4ADF6CE81F8F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c823164dad174c1010e0847e49bba52407814f2c","datavalue":{"value":"1300.05113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396945$6A47749F-30B4-4A3F-88A8-40E1D67BC2E2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1e4e97dfff3e8c3bc0ef1c4bf7de5b4d7c5b8b65","datavalue":{"value":{"entity-type":"item","numeric-id":354433,"id":"Q354433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$F818ADFA-2321-445F-9DF6-AA2001328CEF","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":"Q396945$1B12D6EB-2683-4FD0-95CB-BC94CCC51110","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"014386d1e7349618004d8e2aa9650d7520cb60bd","datavalue":{"value":{"time":"+2014-08-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q396945$3E1FF5FC-7E45-46BB-AAA2-EF0CAFDEE6B8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8c7371ec7efadb1250f7694e251f855358e1aad4","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p23","type":"string"},"datatype":"url"},"type":"statement","id":"Q396945$9513DA2F-5040-49CD-AFF0-C792B7E713BB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6d9d8beb3fe894cae8bb660440eb4e2d4fea34f2","datavalue":{"value":"Summary: A digraph \\(D\\) is traceable if it contains a path visiting every vertex, and hypotraceable if \\(D\\) is not traceable, but \\(D-v\\) is traceable for every vertex \\(v\\in V(D)\\). \\textit{S. A. Van Aardt} et al. [Discrete Math. 311, No. 14, 1273--1280 (2011; Zbl 1225.05122)] showed that there exists a hypotraceable oriented graph of order \\(n\\) for every \\(n\\geq 8\\), except possibly for \\(n=9\\) or \\(11\\). These two outstanding existence questions for hypotraceable oriented graphs are settled in this paper -- the first in the negative and the second in the affirmative. Furthermore, \\(D\\) is \\(k\\)-traceable if \\(D\\) has at least \\(k\\) vertices and each of its induced subdigraphs of order \\(k\\) is traceable. It is known that for \\(k\\leq 6\\) every \\(k\\)-traceable oriented graph is traceable and that for \\(k=7\\) and each \\(k\\geq 9\\) there exist nontraceable \\(k\\)-traceable oriented graphs of order \\(k+1\\). The traceability conjecture states that for \\(k\\geq 2\\) every \\(k\\)-traceable oriented graph of order \\(n\\geq 2k-1\\) is traceable.    In this paper it is shown via computer searches that all 7-traceable and 8-traceable oriented graphs of orders \\(9, 10\\) and \\(11\\) are traceable, and that all 9-traceable oriented graphs of order \\(11\\) are traceable. All hypotraceable graphs of order \\(10\\) are also found. Recently, these results are used to prove that the traceability conjecture also holds for \\(k =7, 8\\) and 9, except possibly when \\(k=9\\) and \\(22\\leq n\\leq 32\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q396945$967517AD-A929-4F6B-BE74-3EE98A03582C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396945$BEB3E379-6735-467E-AC96-ADBE6310C0C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396945$59B7C86F-CB2F-4B97-AA75-3A10441028C8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"de0e65eea44cc0c9989a33cf8ac358988bb4129a","datavalue":{"value":"6330354","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396945$A5081713-6939-4C9B-8E52-47F3AE2D2D21","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d88254a5760b31b61e1fb0129d8fa4b56625290","datavalue":{"value":"oriented graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q396945$87141D56-E230-4F4D-ABC8-D3DBCFBB5CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1db92bc7601eaee178ffaed0103e4107bc22c468","datavalue":{"value":"tournament","type":"string"},"datatype":"string"},"type":"statement","id":"Q396945$21A5D520-0E96-4971-8BEE-C1726008BEFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b72afd3f8e7e0dc0844e2cca6bc65fd61aa8fd1b","datavalue":{"value":"hypotraceable","type":"string"},"datatype":"string"},"type":"statement","id":"Q396945$1873323A-4795-4356-8F5E-0920B6ADB58F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef0984f79ec98eb27acd8c0453d1418a56010f15","datavalue":{"value":"\\(k\\)-traceable","type":"string"},"datatype":"string"},"type":"statement","id":"Q396945$B167E85D-214C-4D5D-8AD8-0DA2C611D295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"924607da8efe2573a9e8496cc49b2d127a27106e","datavalue":{"value":"traceability","type":"string"},"datatype":"string"},"type":"statement","id":"Q396945$CD081FB8-63A8-49A5-8604-E5C282A28167","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":"Q396945$C1CDFAEF-A340-4372-94FA-7ABFC5E44D67","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1d4c657f988b819627ab8864327408c13bf9ea2","datavalue":{"value":{"entity-type":"item","numeric-id":1953448,"id":"Q1953448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$F7D9ACC2-CEDA-4BEB-B196-2E669169E612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0eb3382b3dc81d5167bcb8b8f23564551d92c342","datavalue":{"value":{"entity-type":"item","numeric-id":5492647,"id":"Q5492647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$F7C0C6BA-0D0A-4D6F-BACA-6285759CB391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1648ade3edd7e8911e0213d4d10fa1dcb749262d","datavalue":{"value":{"entity-type":"item","numeric-id":965994,"id":"Q965994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$A70F927C-DC7D-405E-8511-C4E95B898B3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"182dff32abd3746f92ff04072eb2e2ed57c19b4c","datavalue":{"value":{"entity-type":"item","numeric-id":641171,"id":"Q641171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$5D3D8554-0970-4CD5-B273-6044AEA3E34B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf27a3a17462a1e357558955de1a851b63219790","datavalue":{"value":{"entity-type":"item","numeric-id":1010888,"id":"Q1010888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$D906D50D-1CEA-494E-A11A-491BFAE30D28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"867ac5df28d54c4379ce8e9a0ea9247d97b09a81","datavalue":{"value":{"entity-type":"item","numeric-id":2275358,"id":"Q2275358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$7E9BAF9D-8A29-4F9A-8BB5-CF8A95A6D2E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebade38ddfaf89228b6b45ac4d3ced1aae55aa16","datavalue":{"value":{"entity-type":"item","numeric-id":2501556,"id":"Q2501556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$AEE116A3-443C-4EE6-A5D1-BC8276E5BAA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e69e32f0d3231644ec9608af720173f67dd912b9","datavalue":{"value":{"entity-type":"item","numeric-id":3575434,"id":"Q3575434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$902923FA-5B42-490D-A642-BF494FC2BE36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9c4945856254e0cf3bac6b29d0f87126f60e28a","datavalue":{"value":{"entity-type":"item","numeric-id":2427505,"id":"Q2427505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$EF38FE85-20CC-4365-9F01-8C26D31F7FF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cceeade35f679406477b200113c98fd68dc2e52e","datavalue":{"value":{"entity-type":"item","numeric-id":1917489,"id":"Q1917489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$AD291E95-0D46-44A1-8720-55331427995F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fa18203666e786a7666e664381554f99e170586","datavalue":{"value":{"entity-type":"item","numeric-id":1147716,"id":"Q1147716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$5B2BBF2A-DCF4-41B1-91B8-514DA1F02434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c27060754581911527caacd54b2cca4cb14c4552","datavalue":{"value":{"entity-type":"item","numeric-id":3920990,"id":"Q3920990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$EB6D56E6-93ED-4A24-820C-ECC093BBE052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7df3d33b2e8b1f61e7d4c52554004f6e5e0552d","datavalue":{"value":{"entity-type":"item","numeric-id":1763350,"id":"Q1763350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$896DCEB8-2C4F-4850-86FB-63DCB6A8D751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1353d2952977fbf18a6627382605f90076a5b95b","datavalue":{"value":{"entity-type":"item","numeric-id":3309863,"id":"Q3309863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396945$E5F81E59-A113-4D76-9152-ACC2A4BDEE35","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48cc5012360450fb5a02e6eb4aae570b4ff6adb4","datavalue":{"value":{"entity-type":"item","numeric-id":2275358,"id":"Q2275358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10361659985181a784578ec7554388d439c375b3","datavalue":{"value":{"amount":"+0.9064690470695496","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":"Q396945$D2383F84-DF04-45C8-B556-2751C9AA9C83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"974f03f2deabf7447693ed6fc518f77638c52698","datavalue":{"value":{"entity-type":"item","numeric-id":965994,"id":"Q965994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b1803e4428370115b344bf09f7b2d44bc8a38ab","datavalue":{"value":{"amount":"+0.8989453315734863","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":"Q396945$388FB8D2-57C1-44EC-A6DB-EE787CB2D52E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f55e00b97032c4ac1e8d55c02acaa96cf72f8c5f","datavalue":{"value":{"entity-type":"item","numeric-id":2409787,"id":"Q2409787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b8dc19afdd31ea774e605121c3ffc47e6714470","datavalue":{"value":{"amount":"+0.8932084441184998","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":"Q396945$9B94B331-AD70-4DCD-8C98-70E679F21E57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61234b3a33b4a76c79aad5de0fc03ee639301911","datavalue":{"value":{"entity-type":"item","numeric-id":3575434,"id":"Q3575434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"add223a4323dd7ece4dd812ac573a9c382e6389e","datavalue":{"value":{"amount":"+0.89044588804245","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":"Q396945$A9A9BB25-90EB-4669-9C08-F05832B1A683","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f037357b0caefbc4eb928f23b81026c3b8397140","datavalue":{"value":{"entity-type":"item","numeric-id":895060,"id":"Q895060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd838a658969f9e5fff7e9f45084321de18535a6","datavalue":{"value":{"amount":"+0.8816476464271545","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":"Q396945$02AF364B-9B3F-47BD-9415-C17104A05502","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:396945","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:396945"}}}}}