{"entities":{"Q2151226":{"pageid":2161969,"ns":120,"title":"Item:Q2151226","lastrevid":57233892,"modified":"2026-03-27T14:25:32Z","type":"item","id":"Q2151226","labels":{"en":{"language":"en","value":"Extremal digraphs avoiding distinct walks of length 4 with the same endpoints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7551401"}},"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":"Q2151226$22116C8F-86D3-4684-AC44-AC59BE47BC2B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8a51e81b57710797f90aa886f44f1da087bf58d1","datavalue":{"value":{"text":"Extremal digraphs avoiding distinct walks of length 4 with the same endpoints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2151226$A66B59F1-CBB8-4F1D-BF38-16B1DC4DC13C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"15ebafa57c865b0e2dd86db1c310196e97cdcc83","datavalue":{"value":"1497.05106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2151226$B8C6565D-C4AB-45C1-9D89-827610891CC1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"15d92303771e3b717dc86b2d98af72b1ddc2b418","datavalue":{"value":{"entity-type":"item","numeric-id":1736212,"id":"Q1736212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151226$6F89A737-4D91-4CEF-9AC5-BB42F9771312","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b01f91c2828ea0406533259953e45b7596e1cea7","datavalue":{"value":{"time":"+2022-07-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2151226$17175A49-C06E-4B64-B9AA-6C6EE85CB015","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7a239f8b1f8643cd5125c4f1fa6f0d8e04ebe531","datavalue":{"value":"For positive integers, \\(n\\) and \\(k\\), consider simple digraphs \\(D\\) of order \\(n\\) that do not contain two different walks of length \\(k\\) with the same initial vertex and the same terminal vertex. In 2007, \\textit{X. Zhan} posed the problem of determining the maximal size of such digraphs and determining the structure of such digraphs with this maximal size; for more details [Matrix theory. Providence, RI: American Mathematical Society (AMS) (2013; Zbl 1275.15001)].  Both parts of the problem have since been solved for all \\(k\\neq 3,4\\), and the maximal size has been found for \\(k=4\\); see [\\textit{Z. Huang} et al., Discrete Math. 342, No. 6, 1703--1717 (2019; Zbl 1414.05133); \\textit{Z. Huang} and \\textit{X. Zhan}, ibid. 311, No. 1, 70--79 (2011; Zbl 1225.05115)].  The author of the present paper completes the solution to the problem for \\(k=4\\) and all \\(n\\geq k\\) by finding the maximal-sized simple digraphs of order \\(n\\) containing no two walks of length \\(4\\) with the same initial and terminal vertices. For \\(n\\geq 12\\), these are shown to be particularly nice and simple to describe: they are the balanced \\(4\\)-partite transitive tournaments.  The author also poses the related problem: what is the maximal size of a simple digraph of order \\(n\\) that contains at least one walk of length \\(k\\) but does not contain two different walks of length \\(k\\) with the same initial vertex and the same terminal vertex. This problem is interesting because none of the extremal digraphs for Zhan's problem contain a walk of length \\(k\\) when \\(n\\) is large, at least for the so-far solved cases \\(k\\neq 3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2151226$9F0CDC5E-B04A-4868-8830-826F302B2181","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2151226$EB0F2AD6-1E88-40F6-BD45-F1B7644FCE86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2151226$25BAD8F0-0E86-4127-8DB3-6470FCB0AFA0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dc248096b50cebc6d5591235f42d73c70fa3b9f1","datavalue":{"value":"7551401","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2151226$00F912A3-A84A-47A5-B155-2AD48C1D5AE3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2151226$87273830-A702-4018-8433-5E849F92A119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"caa0e78be6e65479f916635f0e2ef74a5e556ee0","datavalue":{"value":"Tur\u00e1n problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2151226$3B2BD735-8A0B-4F37-82CA-3893EC6D1B0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1cef4886cd87e3dd0ff9c6187d84ddbd09840f6","datavalue":{"value":"transitive tournament","type":"string"},"datatype":"string"},"type":"statement","id":"Q2151226$C23D35DB-31A4-4922-9244-3CBCC7E69AF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"65bd34070aaf54b27536b874611d93a4ce51fc08","datavalue":{"value":"walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q2151226$97E5E1A5-3B7E-4B6F-A0F4-A098A9CE6B66","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4b6daa67a0e42b208d8b116bb9a44ab2f9a975bd","datavalue":{"value":{"entity-type":"item","numeric-id":189835,"id":"Q189835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151226$226A6DE9-CBDA-438D-8C0B-11B93703B036","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":"Q2151226$38C404F2-2956-4D5A-B7A8-811A5BDFCF6B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"952590fe6529ece495bcb4f4c8cc6a485ce81698","datavalue":{"value":"https://doi.org/10.7151/dmgt.2321","type":"string"},"datatype":"url"},"type":"statement","id":"Q2151226$19165871-5053-4350-A717-2AFD8C1E5352","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"365636429834571b1eb525387d8793e4ef5cbf5f","datavalue":{"value":"W3023262794","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2151226$732D3851-1442-428C-8F57-AB0AB0925C00","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ca2deb622e66d040141c5d3946d3754cbb145c9","datavalue":{"value":{"entity-type":"item","numeric-id":2557710,"id":"Q2557710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151226$C8009459-F6C5-427F-BEFF-0D3704239B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36eed8e70d9a0309e00780725737b36d21ad297e","datavalue":{"value":{"entity-type":"item","numeric-id":5610936,"id":"Q5610936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151226$416E5EF3-18DC-44F9-9C51-D1BEA6A233F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"386dac21b6089029bbdb799213ef371365147c3a","datavalue":{"value":{"entity-type":"item","numeric-id":5132619,"id":"Q5132619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151226$C61434B1-281D-423F-AAEF-78D8C45B14CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daefd2961872addab0dd19742311ca2987a1a87e","datavalue":{"value":{"entity-type":"item","numeric-id":1999736,"id":"Q1999736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151226$B987ACBC-3541-4B4A-8B7D-9696645C36D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45900f9aacff42057cca7da80c8d6c2ae236bf3e","datavalue":{"value":{"entity-type":"item","numeric-id":616364,"id":"Q616364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151226$7C6D3F70-A37A-410B-81CA-1A518DB6BF6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abf3b0e5375d70182e3587fde7c849c7323acab1","datavalue":{"value":{"entity-type":"item","numeric-id":967506,"id":"Q967506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151226$6A8D4463-92A0-465E-A109-403A67FA1B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e85905c71e340d776f1b8fec14b4054bad6866fa","datavalue":{"value":{"entity-type":"item","numeric-id":2840668,"id":"Q2840668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151226$3BABFC19-A855-4B20-AC99-1A39FFCBB662","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"af63fca8a97558aa039431158aaa6e3fcec4c32a","datavalue":{"value":"10.7151/DMGT.2321","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2151226$E05A9B25-A596-46D9-90CC-5185762AE97B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"836368b6337657a52f201de441b98aececc2523a","datavalue":{"value":{"entity-type":"item","numeric-id":2725179,"id":"Q2725179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151226$6015802C-4FA8-4F6C-90A8-D4E704936E87","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2dd7f8f2c8e8c17bb1e8dc634e63fe54a4d2063","datavalue":{"value":{"entity-type":"item","numeric-id":1999736,"id":"Q1999736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41c61d8a5ca7686a53557bed319306611c544c1f","datavalue":{"value":{"amount":"+0.92034113407135","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":"Q2151226$8EF446C9-ABC4-4CF3-9717-BCC5747A6663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14c80828395958680ed123de30569720c6a624a5","datavalue":{"value":{"entity-type":"item","numeric-id":2144591,"id":"Q2144591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3275b458b937d59ca2679cd1806d720c8cd3049","datavalue":{"value":{"amount":"+0.9046883583068848","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":"Q2151226$E8466A48-E521-4D4A-AFA4-6C47345F1380","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0072b93a2d1c9eb825b184380f206fd5fc7f1b41","datavalue":{"value":{"entity-type":"item","numeric-id":442298,"id":"Q442298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74d02e1882c65bbd1fb496438cac419ba8899906","datavalue":{"value":{"amount":"+0.8950495719909668","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":"Q2151226$36D104B7-D3C3-46AD-AF8A-DE62F5E0FCA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d580bd4054db0cee176254632a3a6fe893fabd7b","datavalue":{"value":{"entity-type":"item","numeric-id":2025066,"id":"Q2025066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f98b32a9b2e89f29a3b3af20530a0535a7318c4","datavalue":{"value":{"amount":"+0.8575851321220398","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":"Q2151226$DFB85174-DB04-4041-B226-E5B9FDF6C290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee687fc8cbfca28061c1814b40582ddd6630b5a5","datavalue":{"value":{"entity-type":"item","numeric-id":2115146,"id":"Q2115146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5b25f69afe4447f55251fc5118df2230d2f8555","datavalue":{"value":{"amount":"+0.8480339646339417","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":"Q2151226$3D7E57C0-D4DD-45A5-830D-F0B6B3ABD480","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"6e2260e47a2889770c9d5516a7c5ae827b188d2b","datavalue":{"value":{"entity-type":"item","numeric-id":6830563,"id":"Q6830563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151226$DAB65CA1-7F27-47BE-A5B7-4F1DF2F8C0EE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2151226","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2151226"}}}}}