Every tree is 3-equitable (Q1567631)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Every tree is 3-equitable |
scientific article |
Statements
Every tree is 3-equitable (English)
0 references
29 January 2001
0 references
A labeling of a graph \(G=(V_G,E_G)\) is a mapping \(f\) of \(V_G\) to natural numbers. Define the labels of an edge \(uv\in E\) as \(|f(u)-f(v)|\). A labeling is called \(k\)-equitable if the image of \(f\) is \(\{0,1,\dots,k-1\}\) and if \(v_i\) denotes the number of vertices labeled \(i\) and \(e_i\) is the number of edges labeled \(i\) then \(|v_i-v_j|\leq 1\) and \(|e_i-e_j|\leq 1\) for all \(i,j\in\{0,1,\dots,k-1\}\). It is shown that every tree is 3-equitable by providing a labeling algorithm.
0 references
tree
0 references
graph labeling
0 references