{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:44:15Z","timestamp":1753893855182,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>The Pr\u00fcfer code is a bijection between trees on the vertex set $[n]$ and strings on the set $[n]$ of length $n-2$ (Pr\u00fcfer strings of order $n$).  In this paper we examine the 'locality' properties of the Pr\u00fcfer code, i.e. the effect of changing an element of the Pr\u00fcfer string on the structure of the corresponding tree. Our measure for the distance between two trees $T$ and $T^*$ is $\\Delta(T,T^*)=n-1-\\vert E(T)\\cap E(T^*)\\vert$.  We randomly mutate the $\\mu$th element of the Pr\u00fcfer string of the tree $T$, changing it to the tree $T^*$, and we asymptotically estimate the probability that this results in a change of $\\ell$ edges, i.e. $P(\\Delta=\\ell\\, \\vert \\, \\mu).$ We find that $P(\\Delta=\\ell\\, \\vert \\, \\mu)$ is on the order of $ n^{-1\/3+o(1)}$ for any integer $\\ell&gt;1,$ and that $P(\\Delta=1\\, \\vert \\, \\mu)=(1-\\mu\/n)^2+o(1).$ This result implies that the probability of a 'perfect' mutation in the Pr\u00fcfer code (one for which $\\Delta(T,T^*)=1$) is $1\/3.$<\/jats:p>","DOI":"10.37236\/99","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T04:36:34Z","timestamp":1578717394000},"source":"Crossref","is-referenced-by-count":1,"title":["On the Locality of the Pr\u00fcfer Code"],"prefix":"10.37236","volume":"16","author":[{"given":"Craig","family":"Lennon","sequence":"first","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2009,1,23]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v16i1r10\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v16i1r10\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,18]],"date-time":"2020-01-18T03:14:26Z","timestamp":1579317266000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v16i1r10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,23]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2009,1,7]]}},"URL":"https:\/\/doi.org\/10.37236\/99","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2009,1,23]]},"article-number":"R10"}}