{"entities":{"Q1970584":{"pageid":1981326,"ns":120,"title":"Item:Q1970584","lastrevid":82264271,"modified":"2026-05-06T20:29:25Z","type":"item","id":"Q1970584","labels":{"en":{"language":"en","value":"On traceable powers of digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1420219"}},"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":"Q1970584$4FB5F730-2857-4F43-952E-7BD8029CF1FB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e7334b158d9f0d497613e7ba2dc2cef673bb7cac","datavalue":{"value":{"text":"On traceable powers of digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1970584$15DC554B-51AD-4572-B709-D8B339E9A916","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e0dc7f06b26c27b7d14e38f063edea52e1c7cbb9","datavalue":{"value":"0940.05034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1970584$CD93C147-37A4-4B37-B554-8A7426C270A2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"df342dd4781629c0d3338bd85d3a866c09ef4900","datavalue":{"value":"10.1016/S0012-365X(99)00213-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1970584$8C790364-B70F-4C06-93DB-4CACAC66C24B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9416fd95f386fce4530359486a7afb51aa750b0d","datavalue":{"value":{"entity-type":"item","numeric-id":367073,"id":"Q367073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1970584$7D7788A2-18D2-4C02-8F07-1230ABDC1E8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb0ea6b8f0923628999c2cb0ffc422a2366b8cc9","datavalue":{"value":{"entity-type":"item","numeric-id":878647,"id":"Q878647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1970584$4CD92819-529D-4E96-BF0C-EAAE204EEFD2","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":"Q1970584$EA3DB635-41D2-478C-B12F-2C6368767798","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4dc3d990a0a8b8ad0b1a8a62e538a71a4d2cf07","datavalue":{"value":{"time":"+2000-07-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1970584$0BDD90DE-7E19-4A9A-AE7D-D647BC2F0B4C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6ad19744fe056d59f5a866052d16ee4558ea55cb","datavalue":{"value":"Let \\(D\\) be a (finite) strongly connected digraph. The \\(m\\)th power of \\(D\\) is the digraph \\(D^m\\) with the same set of vertices as \\(D\\) and an ordered pair \\((x,y)\\) of different vertices is an arc of \\(D^m\\) whenever the directed distance from \\(x\\) to \\(y\\) in \\(D\\) is no more than \\(m\\). A digraph is said to be traceable if it contains a hamiltonian (directed) path. Denote by \\(\\alpha(D)\\) the independence number of a digraph \\(D\\). The authors state the following conjecture: Let \\(D\\) be a strongly connected digraph of order \\(n\\geq 4\\) and \\(m=\\lfloor n/2\\rfloor-1\\). If \\(\\alpha(D^m)\\leq m+1\\) then \\(D^m\\) is traceable. They prove the conjecture for \\(n=2m+2\\) even. Moreover, it is shown that if \\(D\\) is a strongly connected digraph of order \\(n=2m+2\\geq 4\\), then \\(D^m\\) is traceable if and only if \\(D\\) is not isomorphic to a digraph of a family explicitly constructed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1970584$DED30E13-3F03-4477-8C78-C6AFCEE78460","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1970584$337FC370-D56B-4EF3-A27B-03299D28F178","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1970584$D4030CDB-4C1C-4699-A715-B37AB55D4F32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1970584$95E5A60B-5227-4B20-ABE4-9EA623F4F7CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1970584$6B7B2FCF-1E9C-474F-8CB2-B6C5E3D99283","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"77dbee4b838270c86ed2d0da43319c842c4a90a0","datavalue":{"value":"1420219","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1970584$7B5175E2-600B-43EB-A00E-A917FC4A1BCA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1970584$2735C34E-7CE2-4B0F-93ED-5F69DE5C545A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"33e0df2f6c93a5b5d90fd322f70c071feee77d8f","datavalue":{"value":"strongly connectedness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1970584$F3222034-3B9C-438A-BF7E-D55F604A0B78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc0c1332cddac2d1a7b17ff247cd686bbd755c43","datavalue":{"value":"hamiltonian path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1970584$1B42C9EC-5377-4FB5-89D7-CF01DE9ABAB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ec6cafaf78f34592a470a0bda5aa4ea1f712345","datavalue":{"value":"hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1970584$29906D54-045F-494A-8B21-34708C0C47B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"924607da8efe2573a9e8496cc49b2d127a27106e","datavalue":{"value":"traceability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1970584$589733CA-CA34-4C43-B297-DFF9C7041501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0790746f6410ed142073636c3fdda5375d90359","datavalue":{"value":"distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1970584$029F6F99-88DC-425D-BEF2-B500146A14D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbe0ff6f2c2ded3becccda3386525a2ab1c93d20","datavalue":{"value":"power","type":"string"},"datatype":"string"},"type":"statement","id":"Q1970584$A681847F-75EA-4C3F-B43F-E2C8EBDA0F5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1970584$7FFEFCBB-3D08-4FDB-B9F3-5687D4E582AC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"149bbc988a75081535398a6f01834cbcfd6043f6","datavalue":{"value":{"entity-type":"item","numeric-id":588051,"id":"Q588051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1970584$BB265C3F-2578-46F5-B391-94821AF56FC5","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":"Q1970584$3C980EA9-B8DB-4C0D-A2BE-19B59165D158","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3953a4d980afb63dba4874e4b4a68f87141bd80d","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(99)00213-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1970584$00F6A0C2-05C8-4E4B-9013-1A244779C93E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f3c201b8d9461e7cc7df540676db0c125099ab19","datavalue":{"value":"W2056388902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1970584$575809B1-C79C-49B7-A6AB-5AEDF31DEAE2","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"35cb23d3539ec0acbdc556732b2b26603b3bdfeb","datavalue":{"value":"Q128089516","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1970584$D12E2326-B67A-4B9E-AD6F-50E7DD62C044","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ba8612bd7a1d8087041279f5fe59b1c964488e8","datavalue":{"value":{"entity-type":"item","numeric-id":5391578,"id":"Q5391578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"576a6d7eaa23d39bfbb2790ea8f39b2ff7199253","datavalue":{"value":{"amount":"+0.8932831","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":"Q1970584$FB4913B5-1DCD-4FF0-83AC-193A263AB844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"522237e23096418b1a952403f04416412294dda0","datavalue":{"value":{"entity-type":"item","numeric-id":4553420,"id":"Q4553420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e02521a879cc1b39d55c9616f5602a9e2fd83aed","datavalue":{"value":{"amount":"+0.88999915","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":"Q1970584$AC31DBAA-0F86-44DC-B25D-E9200E709C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3fae75ed469d90d191e3825b6047a2624400c27","datavalue":{"value":{"entity-type":"item","numeric-id":2828858,"id":"Q2828858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba83c4f0c2f28fca2d263e90f1a8084b4840e431","datavalue":{"value":{"amount":"+0.88966286","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":"Q1970584$8B2F3A7E-0A6F-4E9C-969E-AE5C0B563B85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a523ae8e25bd87baf90983e282286241fa182f8d","datavalue":{"value":{"entity-type":"item","numeric-id":1972325,"id":"Q1972325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b51b6d923467a869dbbcacbb518d604bd245b48","datavalue":{"value":{"amount":"+0.8860914","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":"Q1970584$30D5BBBE-1D0D-4C3D-B534-DFF5731B7A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8393a9a6d83a6b2993294d1635f8f824b68d0029","datavalue":{"value":{"entity-type":"item","numeric-id":4973667,"id":"Q4973667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c59d1222ac6fa6022165c1e558460de0ef1049c8","datavalue":{"value":{"amount":"+0.88592863","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":"Q1970584$B0487051-EAF9-4810-BCCB-49650C5E2C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a01ff06c245fc4452b533ad2f6a0737999bef34","datavalue":{"value":{"entity-type":"item","numeric-id":3466194,"id":"Q3466194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe7d0ec63f3dd1e056247d4e71ce7807efb4c019","datavalue":{"value":{"amount":"+0.8853187","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":"Q1970584$1CBBA171-236F-4E64-A434-2E80477B5BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43592f702a8a99e340224d1fc728ac0fdd8a585f","datavalue":{"value":{"entity-type":"item","numeric-id":1349073,"id":"Q1349073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8defbcfce6d64b6e55db396408fae6340eb6945","datavalue":{"value":{"amount":"+0.8814641","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":"Q1970584$1AAAD05C-6DCB-4D77-81DB-B6592D4D8FED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a698a989b5da52bccc5e7f85e2284407086fa33c","datavalue":{"value":{"entity-type":"item","numeric-id":4888637,"id":"Q4888637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d83e6d7f68a8f26481eef02fb9f40590cee45a6c","datavalue":{"value":{"amount":"+0.8800379","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":"Q1970584$E001D04C-FA7B-4CD5-B2E3-3BE19EC370B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0010381bb879e63dcde49d903962a349ba6ad4ce","datavalue":{"value":{"entity-type":"item","numeric-id":5121946,"id":"Q5121946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b6b5cdfda627fde2110b590df348cd0f28fa758","datavalue":{"value":{"amount":"+0.8796552","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":"Q1970584$08C44968-F37B-444F-A029-317807E77934","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d866ec417dac6d9f215a7742a7756f1457bef80","datavalue":{"value":{"entity-type":"item","numeric-id":3318807,"id":"Q3318807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3adf90a860b4561f8c77c8c6af618cfe9080b32","datavalue":{"value":{"amount":"+0.87797594","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":"Q1970584$A186EBC0-8D50-474D-AA7F-0709FFE17465","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On traceable powers of digraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_traceable_powers_of_digraphs"}}}}}