{"entities":{"Q1010888":{"pageid":1012736,"ns":120,"title":"Item:Q1010888","lastrevid":66595656,"modified":"2026-04-12T11:11:15Z","type":"item","id":"Q1010888","labels":{"en":{"language":"en","value":"A traceability conjecture for oriented graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5541055"}},"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":"Q1010888$6DF25EDF-6C1F-425F-B853-CBFF367E0D72","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f7f3534596489026062c687787df17326e6a4ebb","datavalue":{"value":{"text":"A traceability conjecture for oriented graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010888$A5D8E035-F71B-4D2A-A877-E4018113C251","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a263895102cbcdf50d98cd575386956f55911916","datavalue":{"value":"1178.05046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010888$9B4DA1BF-350E-4869-AD9A-80B35A65A73C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fc6e1be8090e1bf9e3724ced36f209cc459d004c","datavalue":{"value":{"entity-type":"item","numeric-id":976760,"id":"Q976760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010888$C92A6E9E-B081-4372-B52F-975C83861290","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":"Q1010888$35CE1C6A-56EF-45A0-B912-30AD5D411A44","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-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":"Q1010888$DD25DA0E-38E4-46B0-B3D5-C069F4053D36","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9e93c92cc3b4e9c00124e5ce23fd170cd39ccf39","datavalue":{"value":"https://eudml.org/doc/117284","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010888$A54A4DBC-6AC0-4611-8BBF-89661814F57B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"f06ef1f7b6a7f52ce97790052c00a64dcb74c83b","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r150.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010888$B84F4201-B7AF-4659-92CD-3CE30333FE03","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3aa2dadc325a38a87093e8eba7c62de52f40c359","datavalue":{"value":"Summary: A (di)graph \\(G\\) of order \\(n\\) is \\(k\\)-traceable (for some \\(k\\), \\(1\\leq k\\leq n\\)) if every induced sub(di)graph of \\(G\\) of order \\(k\\) is traceable. \\ It follows from Dirac's degree condition for hamiltonicity that for \\(k \\geq 2\\) every \\(k\\)-traceable graph of order at least \\(2k-1\\) is hamiltonian. The same is true for strong oriented graphs when \\(k=2,3,4,\\) but not when \\(k\\geq5\\). However, we conjecture that for \\(k\\geq2\\) every \\(k\\)-traceable oriented graph of order at least \\(2k-1\\) is traceable. The truth of this conjecture would imply the truth of an important special case of the Path Partition Conjecture for Oriented Graphs. In this paper we show the conjecture is true for \\(k \\leq 5\\) and for certain classes of graphs. In addition we show that every strong \\(k\\)-traceable oriented graph of order at least \\(6k-20\\) is traceable. We also characterize those graphs for which all walkable orientations are \\(k\\)-traceable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010888$7B3F71D6-D463-4169-9C7D-CDFCEDD94505","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010888$E72CB68E-C47E-475F-9EA5-B821F21C37FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010888$F67D9FDF-ABED-44E0-AB8E-859E18136783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010888$F72D28EA-88A7-4A86-A412-E30F7B156E26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010888$672F47BD-B28B-433B-B94E-359628A18222","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"22b8f86fb9d6997315165a35510d518b8cfa2e1f","datavalue":{"value":"5541055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010888$653215AD-BC9D-41F4-B08B-600A9EA24846","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6891980e132648b5512af1f4a7a56f6735c9286c","datavalue":{"value":"traceable graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010888$431C8DA5-9DBB-403F-8D36-4100175FBFFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1717c1c9055d9f489b758272396e466c8cfd8e78","datavalue":{"value":"traceable digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010888$AA855500-94F2-4123-A7A2-7ABC183D743D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"924607da8efe2573a9e8496cc49b2d127a27106e","datavalue":{"value":"traceability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010888$AD4A9D4B-5D03-45F5-8631-7FC2F4239F2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ad7f6c16e18413af432f8e820582fb2aa296646","datavalue":{"value":"hamiltonicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010888$8C0283B1-9AFF-4E8C-84D3-642779589215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a82e5042bc8e8b4dcb6c1dff69ae5ae8fb8e33e","datavalue":{"value":"hamiltonian graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010888$8DFC77E9-FEA5-48B9-88D8-8F17E06B5B40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d574120daec4c165587e8da93a89333a82ea7d96","datavalue":{"value":"strong oriented graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010888$090A1960-23BA-49BB-BC91-A7CB31813127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"789751a53a0ca4206150e8fa89a6e44c89150b9d","datavalue":{"value":"path partition conjecture for oriented graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010888$C171F8A7-95DB-44DC-B85B-92651F73C8E0","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":"Q1010888$C7131B4E-4F8E-46FB-98DE-1D68F3055891","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"0cf399e459e975a5162f130c89a4bbe2bf6401f4","datavalue":{"value":"bafkreia7azwemczvbbmo7mu3xi3xavnnc7227juh5uzv4qw4frxih6bchu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010888$9D7E0F01-8BB5-4624-B037-082E1A763FF5","rank":"normal"}],"P1643":[{"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":"eb3bd82bd5f442fb12381d003161a3a5c4a27efb","datavalue":{"value":{"amount":"+0.908841073513031","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":"Q1010888$410BFA01-15D3-4FB2-B7E1-53D50B19BEE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d5fa037b6d75e39bcc552bb23b423e15eb794a4","datavalue":{"value":{"entity-type":"item","numeric-id":898141,"id":"Q898141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98a66191d39aa58bab93f92eca97412a30bf8ca6","datavalue":{"value":{"amount":"+0.90680193901062","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":"Q1010888$89C7C5A3-553C-4C07-B397-60B744F3A864","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd8f5fc15ad444385cf7be8ac43c5d69af3eea15","datavalue":{"value":{"entity-type":"item","numeric-id":641171,"id":"Q641171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"905edff677859321082d3bb1df2fb500308fbbf1","datavalue":{"value":{"amount":"+0.9056599140167236","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":"Q1010888$96971331-FD91-4763-9679-F10785520DE3","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":"86d75b8e6e011f4bce427afd8deff4f0290ddd40","datavalue":{"value":{"amount":"+0.8964258432388306","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":"Q1010888$375B720F-741D-4A1D-8462-7025FD582D33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"606cb0ab83aead86daf5a0e537ec9832b1557ba7","datavalue":{"value":{"entity-type":"item","numeric-id":2848806,"id":"Q2848806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2fe0e3ed705276a83baafb7da9abb2d16004973","datavalue":{"value":{"amount":"+0.8888095021247864","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":"Q1010888$863CC60A-3B18-43C8-A5A8-E1B28AD4DAA2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A traceability conjecture for oriented graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_traceability_conjecture_for_oriented_graphs"}}}}}