Unlabeled graph and graph invariants.

Question

I have somehow a problem to grasp formally a graph invariant on an unlabeled graph.

Formally, it may not make much sense to have an invariant on an isomorphic class, as which I consider an unlabeled graph - at least for the time being.

I somehow already fail to say whether a labeling is an invariant or not, since a labeling seems to be the requirement to have a graph invariant at all. So, I assume, this thought does not make much sense either.

However, given now such a labeling $l : V(G) \to \mathbb{N}$ for a graph $G \in \mathbb{G}_n$, where $\mathbb{G}_n$ denotes all simple graphs on $n$ vertices. Is there any trivial function $S : \mathbb{G}_n \to \mathbb{R}$, such that $S$ is not an invariant and not using (implicitly) the labeling $l$?

Answer 1

Formally speaking, we are looking for a function $S : \{(G, l) : g \in \mathbb{G}_n, l $ a labelling of $G$$\} \to \mathbb{R}$.

We could describe such a function $l$ as follows:

Given $G, l$, we define $S(G, l)$ to be the smallest integer $k$ such that either

1. There exists some $v \in V(G)$, $l(v) = k$, and $v$ has exactly 1 neighbor.
2. There does not exist $v \in V(G)$ such that $l(v) = k$.

Now consider the graph with verticies $a, b, c$ and a single edge, which goes from $a$ to $b$. If we pick the labelling $a \mapsto 0$, $b \mapsto 1$, $c \mapsto 2$, then we have $S(G, l) = 0$. But if we pick the labelling $c \mapsto 0$, $b \mapsto 1$, and $a \mapsto 2$, then we have $S(G, l) = 1$.

Edit:

One can invent all kinds of silly functions which aren't graph invariants. For example, define $S(G) = 1$ if $1$ and $2$ are nodes of $G$ and there is an edge from $1$ to $2$, and $0$ otherwise. But the only functions we care about are those which respect graph isomorphism.