{"entities":{"Q2501577":{"pageid":2512320,"ns":120,"title":"Item:Q2501577","lastrevid":49917811,"modified":"2026-01-12T01:00:07Z","type":"item","id":"Q2501577","labels":{"en":{"language":"en","value":"Minimal rankings and the arank number of a path"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5054430"}},"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":"Q2501577$AE9FBB3C-148E-468B-ADDA-3A76BC69150D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7e331d5f1ccabde7601f5f0bdf4b68b3e6f6af6f","datavalue":{"value":{"text":"Minimal rankings and the arank number of a path","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2501577$48409B6B-726D-480A-A0ED-00F52EAF88E1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"79c0b4074d0a7a1866b2a0370097e78dd80e6115","datavalue":{"value":"1101.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2501577$75EDD6DB-6B72-4E20-AE96-4AF11FDE26C7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bfcec5e2aa4dbec279b8963643c17dc5795033f2","datavalue":{"value":{"entity-type":"item","numeric-id":2501575,"id":"Q2501575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$28FC1A6E-D781-4FD1-A22C-373FB794771D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6487730ae95e38e8db590fae050aca44a2f302c1","datavalue":{"value":{"entity-type":"item","numeric-id":322048,"id":"Q322048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$7AAB9C30-4252-4E73-B826-7F6EF4CC97BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fc97d3311b5179e92734da1012ece225136f10e8","datavalue":{"value":{"entity-type":"item","numeric-id":2501576,"id":"Q2501576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$9588321E-93BF-40A8-A7EB-2608149AE6D5","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":"Q2501577$9311FD9C-BB66-44CB-A4F4-57CFF238F20A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9f4ffc608ada8e4a14c4a7ac75bb9921c404be25","datavalue":{"value":{"time":"+2006-09-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":"Q2501577$68B74E24-C81C-434D-8B02-24CBD3BDE1D3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b813e6700f1c01241f05e6dc0aec02aa16529c88","datavalue":{"value":"A \\(k\\)-ranking of a graph \\(G=(V,E)\\) is a surjective colouring \\(c : V \\to \\{1,2,\\dots,k\\}\\) such that each \\(u\\)--\\(w\\)-path with \\(c(u) = c(w)\\) contains an internal vertex \\(v\\) with \\(c(v) > c(u)\\). A \\(k\\)-ranking is minimal if the reduction of any colour greater than \\(1\\) violates this ranking property. The arank number \\(\\psi_{\\text r}(G)\\) is the maximum value of \\(k\\) such that \\(G\\) has a minimal \\(k\\)-ranking, see e.g.\\ \\textit{J. Ghoshal, R. Laskar} and \\textit{D. Pillone} [Ars Comb.\\ 52, 181--198 (1999; Zbl 0977.05048)].   This note shows \\(\\psi_{\\text r}(P_s) = 2m-2\\) for all \\(s \\geq 2\\) with \\(2^m - 2^{m-2} - 1 \\leq s \\leq 2^m - 2\\), and \\(\\psi_{\\text r}(P_t) = 2m-1\\) for all \\(t \\geq 2\\) with \\(2^m - 1 \\leq t \\leq 2^{m+1} - 2^{m-1} - 2\\), where \\(P_n\\) denotes the path on \\(n\\) vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2501577$F0BA66A6-FAFD-408E-BF0D-E199B761CD24","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2501577$CA6F54C9-8808-4976-A059-36FF6DAE7536","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2501577$5838821F-031B-4E71-8CA0-D250D7A39BEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2501577$B65409A7-1FC5-4E11-9D6E-EC55B12F32E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2501577$E8C00264-3D0A-45C1-AED1-06A5372B144F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f757995179316abfcaf7333ae92bf3f0f7717958","datavalue":{"value":"5054430","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2501577$53668033-F0B6-45B0-A74A-7C3AEA6A0181","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"12f369260896ad84ac09aace07d3d64a29b7a7ae","datavalue":{"value":"vertex ranking","type":"string"},"datatype":"string"},"type":"statement","id":"Q2501577$52A4F880-CFAE-47A2-A8AB-6017EC6F9B59","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":"Q2501577$FA0FA58E-2780-4369-8325-05BC3C75CDE0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0936883512c825c053a457a1eb3fbc852bc2acf8","datavalue":{"value":"https://doi.org/10.1016/j.disc.2006.01.027","type":"string"},"datatype":"url"},"type":"statement","id":"Q2501577$69C7431E-1FAA-4116-832B-94F7FC3B2FE9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4ef59ccec2681b3390f1310ee30337f47dd405dd","datavalue":{"value":"W2099361212","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2501577$07C3C631-60A3-4634-92CA-9143F4420355","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca5549e5a51af06b830af5cab65cab420cc150b7","datavalue":{"value":{"entity-type":"item","numeric-id":4388986,"id":"Q4388986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$D277FEB8-591D-40E5-8F42-420CBA626F8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"945a19422206ac754b8bbbbaa6ca9a9256a6d820","datavalue":{"value":{"entity-type":"item","numeric-id":2931464,"id":"Q2931464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$1420D514-8275-4D27-AEEA-176AEFE0E709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6711167812c082c6d33a39a060fa981ad92ea5f5","datavalue":{"value":{"entity-type":"item","numeric-id":5689817,"id":"Q5689817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$B902E2FD-E00C-4E13-BA2C-EF70B8633936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab22e367a83f0b045ab985f959a2997e30eefc40","datavalue":{"value":{"entity-type":"item","numeric-id":2760998,"id":"Q2760998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$E495E8AA-C7FB-4DBE-A513-0010A5298390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cc36571660ab55293eb11c898c4ddc26281cb71","datavalue":{"value":{"entity-type":"item","numeric-id":1603539,"id":"Q1603539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$BABC5D37-0CA6-43AD-B065-A6162DE36C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b273cf2a0347c3ec1ff8fdcecf03900ec00c2b6","datavalue":{"value":{"entity-type":"item","numeric-id":4470341,"id":"Q4470341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$F08BD3A4-C872-4212-90CE-4D57ADAB00B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c276ea4e5fe31f6e5468162930f40ae807026c17","datavalue":{"value":{"entity-type":"item","numeric-id":3088453,"id":"Q3088453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$76759066-C6A3-4EBF-A7D2-86188D4F969F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2e55133c796ce1553cbbf023c4e3218daac0b08","datavalue":{"value":{"entity-type":"item","numeric-id":4529250,"id":"Q4529250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$6442530B-9D9E-45DF-A2EB-732254DBC4EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e72f83b2f02dabc64cbd88a7ced66f5d6b8084bb","datavalue":{"value":{"entity-type":"item","numeric-id":3089203,"id":"Q3089203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$A0B24DC5-80CB-4C84-BFF4-5AA5D4E94FC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52b73e43baf731d8fb5708ddcd488d937775f5ab","datavalue":{"value":{"entity-type":"item","numeric-id":1199941,"id":"Q1199941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2501577$67F89C85-9DEE-48A3-B5B2-3601A09A398F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"852b12194fce57edd5aaf2908dcb8890dacc80e8","datavalue":{"value":"10.1016/J.DISC.2006.01.027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2501577$36150922-758F-4864-9A55-90CB1F993071","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"825a2838912713594b3c80a80161a66ccedbc9ca","datavalue":{"value":{"entity-type":"item","numeric-id":3089203,"id":"Q3089203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e490633ef4754e6ef9f34a9112b89210974d636a","datavalue":{"value":{"amount":"+0.869916558265686","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":"Q2501577$B760DF01-E711-4211-A799-45BAEFC84395","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57faccceb02439b42665bd0ef8ec9b7c218ac1e8","datavalue":{"value":{"entity-type":"item","numeric-id":1717194,"id":"Q1717194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca71ec9f4cffe1145a3607001bc47f941386ab78","datavalue":{"value":{"amount":"+0.865554690361023","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":"Q2501577$3D8D50B0-4EAE-43DE-B1AB-9A3FF5FBF2FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5efc55dd16bb1ab0b9fff4a16f080a539674dfb7","datavalue":{"value":{"entity-type":"item","numeric-id":2931464,"id":"Q2931464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3794d836ea6ee85413b2e922c5c951eeb75bf778","datavalue":{"value":{"amount":"+0.862313985824585","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":"Q2501577$D8A62FC5-1C65-4DCA-A6E0-299F7F40F109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b15505ec9b04aa306681207ef8f17ceeb8bf9ab6","datavalue":{"value":{"entity-type":"item","numeric-id":4529250,"id":"Q4529250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"373da6afb4017594454c1af29f709165d3c21690","datavalue":{"value":{"amount":"+0.8569720983505249","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":"Q2501577$337828E7-099F-486F-B91D-B8E575CC0A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"797006c308ca47dc81631c8666d181752dba3aec","datavalue":{"value":{"entity-type":"item","numeric-id":2999994,"id":"Q2999994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8202168e21f16baba7e3a3fc581416cdd7c5dec9","datavalue":{"value":{"amount":"+0.8569719791412354","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":"Q2501577$39B18B49-6BC6-4BB0-BA32-579882EED0CA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2501577","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2501577"}}}}}