Function Repository Resource:

# LabeledTreeToPruferCode

Find the Prüfer code associated with a labeled tree

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)
 ResourceFunction["LabeledTreeToPruferCode"][g] gives the Prüfer code associated with the labeled tree g.

## Details and Options

A labeled tree is a tree graph of n vertices where each vertex is uniquely associated with one of the integers 1-n.
For a labeled tree with n vertices, the Prüfer code (also known as the Prüfer sequence and Prüfer numbers) is a list of n-2 integers {i1,i2,,in-2} with 1ijn.

## Examples

### Basic Examples (1)

The Prüfer code of a labeled tree:

 In[1]:=
 Out[1]=

### Properties and Relations (6)

Use FromDigits to obtain an integer-valued Prüfer code:

 In[2]:=
 Out[2]=
 In[3]:=
 Out[3]=
 In[4]:=
 Out[4]=

For a tree with n vertices, the length of the Prüfer code is n-2:

 In[5]:=
 Out[5]=
 In[6]:=
 Out[6]=
 In[7]:=
 Out[7]=

Empty Prüfer code corresponds to a tree with only two leaves:

 In[8]:=
 Out[8]=

The resource function PruferCodeToLabeledTree can be used to reconstruct the tree from its Prüfer code:

 In[9]:=
 Out[9]=
 In[10]:=
 Out[10]=

The Prüfer code of a path is a sequence of n-2 distinct integers:

 In[11]:=
 In[12]:=
 Out[12]=
 In[13]:=
 Out[13]=

The Prüfer code for an n-pointed star with the center vertex k is a sequence of n-1 copies of k:

 In[14]:=
 Out[14]=
 In[15]:=
 Out[15]=

### Possible Issues (2)

LabeledTreeToPruferCode does not work on non-explicit trees:

 In[16]:=
 Out[16]=

Substitute numbers for symbolic values to find the Prüfer code:

 In[17]:=
 Out[17]=
 In[18]:=
 Out[18]=

LabeledTreeToPruferCode accepts only trees with vertices numbered sequentially, starting from 1:

 In[19]:=
 Out[19]=
 In[20]:=
 Out[20]=

Normalize labeling:

 In[21]:=
 Out[21]=
 In[22]:=
 Out[22]=

## Version History

• 1.0.0 – 28 July 2020