{"entities":{"Q896093":{"pageid":897941,"ns":120,"title":"Item:Q896093","lastrevid":65199324,"modified":"2026-04-12T00:58:33Z","type":"item","id":"Q896093","labels":{"en":{"language":"en","value":"Maximizing the number of edges in optimal \\(k\\)-rankings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6520413"}},"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":"Q896093$17FAD34C-0D8A-4AA1-ADCA-968462B84769","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0fa9cf3aa9451c02335f552de411c4f1fc8a2881","datavalue":{"value":{"text":"Maximizing the number of edges in optimal \\(k\\)-rankings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q896093$E5C9BC3A-6043-47C1-A8BA-7CB508246E7E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5eca1d5b03be044586f485f8d8a3ace4266afe3e","datavalue":{"value":"1333.05109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896093$73388C2D-78F9-4D36-A657-D19BA65B6920","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0453f0879fdb7e6be2da726f6df6083d614771c1","datavalue":{"value":{"entity-type":"item","numeric-id":322047,"id":"Q322047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896093$9E306C4C-2A55-4ED8-A66E-1B574F123C13","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":"Q896093$18E8FE1B-DE29-4A8A-836B-054E5A95DCC2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"03e0344fac3b71001f7d01722f599a45a6c3dae0","datavalue":{"value":{"entity-type":"item","numeric-id":321980,"id":"Q321980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896093$A730B68F-60E1-4ABF-A725-10D0AF96CFEB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5f98ff43191c7d2cedf25947a17beeb973f5b0c2","datavalue":{"value":{"time":"+2015-12-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q896093$D00A6DAF-BC9C-4AB0-A980-0839F313E003","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fa38c816ae057a016bf64894eacf388b123bffdf","datavalue":{"value":"https://arxiv.org/abs/1702.02060","type":"string"},"datatype":"url"},"type":"statement","id":"Q896093$8A6AD104-0A77-4E71-8783-F731D9704206","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f2cb61e73d826499f3aa2c514f818d08b4cce4de","datavalue":{"value":"A \\(k\\)-ranking of a graph \\(G\\) is an assignment of the colors \\(\\{1, \\ldots, k\\}\\) to the vertices of \\(G\\) such that whenever \\(v\\) and \\(w\\) receive the same color, every path joining \\(v\\) and \\(w\\) contains a vertex with a larger color. In particular, every \\(k\\)-ranking of \\(G\\) is a proper \\(k\\)-coloring of \\(G\\). The \\textit{rank number} of \\(G\\) is the smallest integer \\(k\\) such that \\(G\\) has a \\(k\\)-ranking; we write \\(\\chi_r(G)\\) for the rank number of \\(G\\). The rank number is monotone when: if \\(H \\subset G\\), then \\(\\chi_r(H) \\leq \\chi_r(G)\\). The paper under consideration studies the following problem: given a graph \\(G\\), how many edges can be added to \\(G\\) without increasing its rank number?   Given a graph \\(G\\) and a ranking \\(f\\), say that a possible edge \\(e \\notin E(G)\\) is admissible for \\(f\\) if \\(f\\) is still a ranking of \\(G+e\\). (This definition of admissibility differs from the definition given in the paper, which is that \\(e\\) is admissible if \\(\\chi_r(G+e) = \\chi_r(G)\\), but appears to be the definition that is required for the correctness of some theorems in the paper, in particular Theorem 8. I have confirmed with the corresponding author that this is the intended definition.)   The authors consider several graph classes for which the optimal ranking \\(f\\) is essentially unique, and show that for each class of graph, we may add all the admissible edges simultaneously and retain the property that \\(f\\) is a ranking. Thus, for these graph classes, the authors determine the exact number of edges that may be added without increasing the ranking number, by counting the size of the set of admissible edges and giving an algorithm to construct this set.","type":"string"},"datatype":"string"},"type":"statement","id":"Q896093$EBEC232B-7A06-414D-966F-75E91BEE169D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cfe23727306a8f36c06e3e9afd90d042a00b5c95","datavalue":{"value":{"entity-type":"item","numeric-id":497322,"id":"Q497322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896093$F52DB1E6-37EF-4679-A207-762B4DAA6C05","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896093$651F6BCD-BCF9-4AA4-92E4-0EE7633F71F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896093$BF01FB37-D281-471D-9B68-FCA24D569DDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896093$74625FBB-2699-4334-B689-D4D576E3140C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3d4283d1e7e696533768f177675fbb2642698450","datavalue":{"value":"6520413","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896093$1B129AF8-1033-4556-8EB3-9B360879AFAA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q896093$F9EBB8A8-7615-4311-BFCA-68147AB7216C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4df73210227f5dfce7acc604ba8e77684da5f9d","datavalue":{"value":"ranking","type":"string"},"datatype":"string"},"type":"statement","id":"Q896093$8E1DE49E-6DA5-43FF-A8E4-D5BC3EF19F82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aebaa00946b71cb533d33dfedf4e158dfb93410f","datavalue":{"value":"minimum \\(k\\)-ranking","type":"string"},"datatype":"string"},"type":"statement","id":"Q896093$A4B17997-786B-4023-BBDF-42F29403B0C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac6894986f6444ae87a1f9a9d17daf668bf5feb7","datavalue":{"value":"maximum number of edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q896093$9B1CE3C3-E913-423A-868A-7D1AC7304ACA","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":"Q896093$56642E66-F7AD-4841-A745-BAC468BB69A2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c1921156122f553aca62892058e639372013a86b","datavalue":{"value":"W1096198614","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896093$12E4D793-6473-4488-A9B9-611C27F40906","rank":"normal"}],"P223":[{"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":"Q896093$389D9630-19F6-4CC6-836F-314FFA6929DF","rank":"normal"},{"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":"Q896093$904F3DE7-EA4E-40F7-AEE8-E936ACD1CF6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a60d00876f4ce3e8944bb22466e70b65fe0fc6c","datavalue":{"value":{"entity-type":"item","numeric-id":712259,"id":"Q712259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896093$761F7145-FBBF-4301-B8E5-97C8940C393F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3eac81c99b20ab0244945b1c675d365243901b7b","datavalue":{"value":{"entity-type":"item","numeric-id":4498984,"id":"Q4498984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896093$12685460-AA0E-4842-B969-4E604DEA47DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36924aa4d29d4f704cce4cf93b299cfc0d05e3c5","datavalue":{"value":{"entity-type":"item","numeric-id":765523,"id":"Q765523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896093$D3F5B115-B3D8-44E9-B80C-33BD5327FAFA","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":"Q896093$40DFD284-A2E8-49B9-8D77-F393781981BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eedbf4b5b9e388d6bff08f5328f1dbbea2cc5cc","datavalue":{"value":{"entity-type":"item","numeric-id":976072,"id":"Q976072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896093$F1647B15-2426-4617-BD24-A420DE1072ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01dcd1a69d5d659f0459c3f7ae943ecba19eb62a","datavalue":{"value":{"entity-type":"item","numeric-id":992551,"id":"Q992551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896093$97F75A94-6C76-4C49-B28E-7B96DDD0A8F0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e20261e59aaf53b8833aa446e352c87b13960712","datavalue":{"value":"10.1016/J.AKCEJ.2015.06.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896093$29180B5D-2E0B-4B1F-9EE2-2EBB99E10602","rank":"normal"}],"P1643":[{"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":"de5901b777d8935e9659ce7df6661f96a0ef9508","datavalue":{"value":{"amount":"+0.8626850843429565","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":"Q896093$731197D9-A778-4F26-BFBC-A65EBAE30221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07b4938e2e0b140c8d60dddc4ad6092c79840288","datavalue":{"value":{"entity-type":"item","numeric-id":5689817,"id":"Q5689817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c0a8e1cf262e806262c91dd0815bcbb441fada4","datavalue":{"value":{"amount":"+0.8626846671104431","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":"Q896093$93D7367D-21B0-4DDA-8585-E51F4ED94FB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdc5183739f916dc329d0a204dea2ab97e534c46","datavalue":{"value":{"entity-type":"item","numeric-id":381188,"id":"Q381188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e9f7f131576066bcbdf298923b38ae124014db8","datavalue":{"value":{"amount":"+0.8269557356834412","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":"Q896093$6E03A4B3-84B9-41F7-B404-38F25CD6FBD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"094d5cbfc9b00efc15025abb0d68f6fb56c1d966","datavalue":{"value":{"entity-type":"item","numeric-id":4388986,"id":"Q4388986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ad909cddd1752fda227255d1721b029f4b5b310","datavalue":{"value":{"amount":"+0.8192481398582458","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":"Q896093$59A961DC-2B88-4615-9F86-38E360F92E41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49264ea32c693ec18df3ccdd3ddb8b3ce9354914","datavalue":{"value":{"entity-type":"item","numeric-id":2760998,"id":"Q2760998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62e6dff73038ccb5b4a1f7a81fab8c566d70feec","datavalue":{"value":{"amount":"+0.8174879550933838","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":"Q896093$067C8CD3-C1D6-49B2-95E5-11F4B5AF6CCD","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"c39a117a349789e54237c0a3254f5a10c0a6517e","datavalue":{"value":{"entity-type":"item","numeric-id":6830565,"id":"Q6830565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896093$42CCD41C-A5EC-4617-A077-0152D0127937","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximizing the number of edges in optimal \\(k\\)-rankings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximizing_the_number_of_edges_in_optimal_%5C(k%5C)-rankings"}}}}}