{"entities":{"Q1408530":{"pageid":1419270,"ns":120,"title":"Item:Q1408530","lastrevid":68635428,"modified":"2026-04-13T01:05:28Z","type":"item","id":"Q1408530","labels":{"en":{"language":"en","value":"Short cycles in digraphs with local average outdegree at least two"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1985367"}},"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":"Q1408530$CBA7F967-14B8-4FA7-9492-43E9E4CEAFD7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7abe70a69315686c84c2ff88b83b979b115c6f78","datavalue":{"value":{"text":"Short cycles in digraphs with local average outdegree at least two","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1408530$826DE2A2-1542-481F-9752-48C6344EFCA2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1d93ba9d07b0351798e5d24de0cb92cd85df900d","datavalue":{"value":"1023.05082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408530$3DAB067A-6673-42EB-86C0-AC70EEF5DEDC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d17693b62e3e0dc43c7191278830d69ad96523cf","datavalue":{"value":{"entity-type":"item","numeric-id":241273,"id":"Q241273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408530$B2E975AB-A78F-46CA-AC9D-FE83F44A6B0C","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":"Q1408530$0F7A8EE8-548B-45BB-A9C9-FBA90017B8CA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ffc36665ea69503c6948e34d2a86d40c9d3697d9","datavalue":{"value":{"time":"+2003-09-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1408530$DE15D0E8-1814-48B1-BDEA-F84511B201AB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"545aa1332d8b3b39d1e87a16f7a4d369ca351a3b","datavalue":{"value":"https://eudml.org/doc/122968","type":"string"},"datatype":"url"},"type":"statement","id":"Q1408530$CD919103-9B31-4C6D-ABB4-1DD12EC3CC64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"2dc542f43b5a8179b969e321316c3a37336858aa","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_10/Abstracts/v10i1r26.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1408530$CD82C789-3D94-42C9-9DE4-F40FBDF4461D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"64829f110b241c82dff126f4776332b7aceafaf7","datavalue":{"value":"Summary: Suppose \\(G\\) is a strongly connected digraph with order \\(n\\), girth \\(g\\) and diameter \\(d\\). We prove that \\(d+g \\leq n\\) if \\(G\\) contains no arcs \\( (u,v)\\) with \\(\\text{deg}^+(u)=1\\) and \\(\\text{deg}^+(v) \\leq 2\\). \\textit{L. Caccetta} and \\textit{R. H\u00e4ggkvist} [Proc. 9th southeast Conf. on Combinatorics, graph theory, and computing, Boca Raton 1978, 181-187 (1978; Zbl 0406.05033)] showed that any digraph of order \\(n\\) with minimum outdegree \\(2\\) contains a cycle of length at most \\(\\lceil n/2\\rceil\\). Applying the above-mentioned result, we improve their result by replacing the minimum outdegree condition by some weaker conditions involving the local average outdegree. In particular, we prove that, for any digraph \\(G\\) of order \\(n\\), if either (1) \\(G\\) has minimum outdegree \\(1\\) and \\(\\text{deg}^+(u) + \\text{deg}^+(v) \\geq 4\\) for all arcs \\((u,v)\\), or (2) \\(\\text{deg}^+(u) + \\text{deg}^+(v) \\geq 3\\) for all pairs of distinct vertices \\(u,v\\), then \\(G\\) contains a cycle of length at most \\(\\lceil n/2\\rceil\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1408530$13113ED6-4B34-4109-A6DE-6CD56EB20D64","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408530$0B36A927-2CD9-48F4-88EA-9358F0B470BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408530$385CEE7F-986A-4DD0-B0FD-0F06CCD06FA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408530$7047E395-2587-47BA-8DC0-3AC3EDD3FBDE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"980556e016fc81e778bceaf8fc2a859641af9785","datavalue":{"value":"1985367","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408530$A340D388-071B-4EF8-8C63-DDC98FFB887D","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":"Q1408530$B24CE5A4-220C-4C30-A13B-2DBCD83C1859","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"bb552671f12d743721eccaa03adc2664762b5e12","datavalue":{"value":"bafkreigapcll3vxhhekwfet65e7oy2j4t3zadwoecbl6bn4bzaptgxex34","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408530$F5926B8C-7E7C-4A2D-A984-0A7B8743790F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34bdb4789e6441ecf6aad9d9954f5e2f7053b0ed","datavalue":{"value":{"entity-type":"item","numeric-id":1112060,"id":"Q1112060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75932ca6973c183bbbec3525400f881b64a8ea89","datavalue":{"value":{"amount":"+0.8539018630981445","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":"Q1408530$3841D11E-5812-4688-AAB9-A3B2CE6B0387","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d5aece7aea4bfaad65acf42b50162caf24cdabf","datavalue":{"value":{"entity-type":"item","numeric-id":1969785,"id":"Q1969785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0aaf3a7b1aa518322748cc86c218350016ef559","datavalue":{"value":{"amount":"+0.832283079624176","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":"Q1408530$C8973E16-B05B-4979-A809-1ED80F65306C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e31ff6e3fd24ba470f8c5daee172129a053c4c9","datavalue":{"value":{"entity-type":"item","numeric-id":1865152,"id":"Q1865152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"984436fbf71baeec1e4d76160672ded1a901b2c2","datavalue":{"value":{"amount":"+0.8286492824554443","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":"Q1408530$10765842-E717-47C4-BFA4-2EFD1B33BB97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"801c6649b7ed9e017d1dfb3576e2f6eab220914d","datavalue":{"value":{"entity-type":"item","numeric-id":712265,"id":"Q712265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41aa9943970791d848ba3df4ea158c50c8df086f","datavalue":{"value":{"amount":"+0.824910581111908","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":"Q1408530$657A1812-6D65-4D6C-951D-78C480E23FA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"146b1052cd723009058178f49a1742eee500e6ca","datavalue":{"value":{"entity-type":"item","numeric-id":5398710,"id":"Q5398710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7605c5e0f3c641b570016a48f1c2950da7b18da6","datavalue":{"value":{"amount":"+0.8199596405029297","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":"Q1408530$7DEA4DFA-B47A-4314-B21F-0F3BC657B199","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Short cycles in digraphs with local average outdegree at least two","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Short_cycles_in_digraphs_with_local_average_outdegree_at_least_two"}}}}}