Given a connected graph $G$ with $V$ vertices and $E$ edges.
I want to assign an ID to each vertex in a way such that the ID combination of each pair of adjacent vertices is unique in the graph.
I was wondering:
1) how many IDs are need of a graph of $V$ vertices? is there any closed-form solution?
2) What if the graph is a planar graph?
Maybe later I’ll be able to go more deeply, but I’ll start from trivial observations. Denote the minimum number of ID’s (which I shall call colors, as it is usual in graph theory) which allows to label the vertices of the graph $G$ satisfying the condition by $r=r(G)$. Then the number of different pairs of colors $r+{r \choose 2}$ is at least $E$. On the other hand, clearly $r\le V$.
I guess that the number $r(G)$ is very dependent on the structure of the graph $G$ and there may be no closed-form solution in the general case.
On the other hand, we can consider some simple graphs.
Let $G$ be a complete graph $K_V$ with $V\ge 3$. It is easy to check that $r(G)=V$. This implies $r(G)\ge\omega(G)$ for each graph $G$, where $\omega(G)$ is the size of the maximum clique in $G$.
Let $G$ be a complete bipartite graph $K_{p,q}$. Then all vertices in each part of the bipartition should have distinct colors, which implies $r(K_{p,q})\ge\max\{p,q\}$. On the other hand, this condition also assures the required coloring, implying that the inequality is, in fact, the equality.