Suggest a Book

# Caterpillars are Graceful

Level: unknown

posted Jun 07 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

Graceful Labeling : Label the vertices of a simple undirected graph $G(V,E)$ (where $|V| = n$ and $|E| = m$) with integers from $0$ to $m$. Now label each edge with the absolute difference of the labels of its incident vertices. The labeling is said to be graceful if the edges are labeled $1$ through $m$ inclusive (with no number repeated). A graph is called graceful if it has at least one such labeling.

• [Easy] : Prove that every graceful graph has at least two graceful labelings.

• [Easy] : Prove that stars, paths are graceful.

• Prove that all caterpillar graphs are graceful.

delete retag edit

## Stats

Posted: Jun 07 '12

Seen: 98 times

Last updated: Oct 24 '12