2025/06/18 by Darling, R. W. R., Fickes, Grant
Computer Science · #05C05 #Advanced Graph Theory Research #Combinatorics (math.CO) #E.1 #Error Correcting Code Techniques #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2506.15796
openalex publication_date 2025/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Prüfer codes provide an encoding scheme for representing a vertex-labeled tree on n vertices with a string of length n-2. Indeed, two labeled trees are isomorphic if and only if their Prüfer codes are identical, and this supplies a proof of Cayley's Theorem. Motivated by a graph decomposition of freight networks into a corpus of vertex-colored rooted trees, we extend the notion of Prüfer codes to that setting, i.e., trees without a unique labeling, by defining a canonical label for a vertex-colored rooted tree and incorporating vertex colors into our variation of the Prüfer code. Given a pair of trees, we prove properties of the vertex-colored Prüfer code (abbreviated VCPC) equivalent to (1) isomorphism between a pair of vertex-colored rooted trees, (2) the subtree relationship between vertex-colored rooted trees, and (3) when one vertex-colored rooted tree is isomorphic to a minor of another vertex-colored rooted tree.