{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:38:47Z","timestamp":1787326727435,"version":"build-2736575974"},"reference-count":6,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>A unique-path labeling of a simple, finite graph is a labeling of its edges with real numbers such that for every ordered pair of vertices $(u,v)$, there is at most one nondecreasing path from $u$ to $v$. In this paper we prove that any graph on $n$ vertices that admits a unique-path labeling has at most $n \\log_2(n)\/2$ edges and that this bound is tight for infinitely many values of $n$. Thus we significantly improve on the previously best known bounds. The main tool of the proof is a combinatorial lemma which might be of independent interest. For every $n$ we also construct an $n$-vertex graph that admits a unique-path labeling and has $n\\log_2(n)\/2 - O(n)$ edges.<\/jats:p>","DOI":"10.1137\/120898528","type":"journal-article","created":{"date-parts":[[2013,7,3]],"date-time":"2013-07-03T16:34:09Z","timestamp":1372869249000},"page":"1228-1233","source":"Crossref","is-referenced-by-count":2,"title":["On the Maximum Density of Graphs with Unique-Path Labelings"],"prefix":"10.1137","volume":"27","author":[{"given":"Abbas","family":"Mehrabian","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dieter","family":"Mitsche","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pawe\u0142","family":"Pra\u0142at","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,7,3]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.07.021"},{"key":"atypb2","unstructured":"J.C. Bermond, M. Cosnard, and S. P\u00e9rennes,<i>Directed Acyclic Graphs with Unique Dipath Property<\/i> Technical report RR-6932, INRIA, 2009."},{"key":"atypb3","unstructured":"M. Bode, B. Farzad, and D. Theis,<i>Good Edge-Labelings and Graphs with Girth at Least Five<\/i> preprint, arXiv:1109.1125, 2011."},{"key":"atypb4","unstructured":"G. H. Hardy, J. E. Littlewood, and G. Polya,<i>Inequalities<\/i> Cambridge University Press, London, 1934."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/0203020"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/11085414X"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120898528","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:35:17Z","timestamp":1787322917000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120898528"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":6,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/120898528"],"URL":"https:\/\/doi.org\/10.1137\/120898528","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}