Number of Labels used in reduction of Isomorphism of Labelled Graph to Graph Isomorphism

Question

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann ,

Assume that both $X$ and $X'$ have $n$ vertices. We plan to code the graph labels as suitable subgraphs which we attach to the vertices of $X$ and of $X'$. In time polynomial in the length of the input we can rename the labels and may assume, therefore, that $L = \{1 ..... k\}$ is the set of labels assigned by $\lambda$ and $\mu$. Note that $k\leq2n$ .We describe how to construct $Z$ from $(X,\lambda)$. The construction of $Z'$ is done in the same way. Let $X = (V,E), V = \{v_1..... v_n\}$. Intuitively, we obtain $Z$ from $X$ by attaching to each vertex $v_i$ a complete graph with $n + r$ vertices, where $\lambda (v_i) = r$. Note that $r\leq2n$. The vertices of the attached complete graph will be, for $v_i$, $\{v_{(i,1)},..... v_{(i,n+r)} \}$ The subgraph is atached to $v_i$ by an edge $(v_i, v_{i,1})$.

It is easy to see that $(X,\lambda)$ is isomorphic to $(X,\mu)$ iff $Z$ is isomorphic to $Z'$. Since there are at most $2n$ distinct labels, the graphs $Z$ and $Z'$ have no more than $2n^2+n$ vortices each and can thus be constructed in polynomial time.

the definition of graph label is given as-

Let $X = (V,E)$ be a graph, $\lambda$ is a mapping from $V$ onto a set $L = \{ l_1,...l_k\}$. Then the pair $(X,\lambda)$ is a labelled graph.

Question 1: Why $k\leq 2n$ which implies $r\leq2n$? It seems that it should be $k\leq n$ since the passage of wikipedia here tells

When used without qualification, the term labeled graph generally refers to a vertex-labeled graph with all labels distinct. Such a graph may equivalently be labeled by the consecutive integers $\{1, …, > |E |\}$, where $|E |$ is the number of vertices in the graph.

Question 2: What is the explanation of -

Since there are at most $2n$ distinct labels, the graphs $Z$ and $Z'$ have no more than $2n^2+n$ vortices each and can thus be constructed in

Thanks in advance.

Answer 1

I think the answer of Jim is good. $k\leq 2 n$ because you have to consider both $\mu$ and $\lambda$. If they have different labels the total number of unique label can be $2n$. (Of course one can argue that if $\lambda$ and $\mu$ does not share the same set of labels that $(X,\lambda)$ and $(X',\mu)$ have no chance to be isomorphic, thus you could first look whether $\mu$ and $\lambda$ share the same labels and then consider $k\leq n$. But that is not the point of the proof here.)

For your second question it is an upper bound of the worst case scenario which gives the bound $2n^2+n$.

The intuition of the proof is to encode the labels of $(X,\lambda)$ and $(X',\mu)$ by connecting the vertices to new fresh vertices. To do this they assume that the labels are between $1$ and $2n$ (which is the first part that confused you). Then they encode that a vertex $v$ has label $j$ by connecting $v$ in $Z$ to $j$ new vertices (note that only $v$ will be connected to this vertices).

So you have to introduce $\lambda(v)$ new vertices for each $v\in X$ in order to build $X$. Thus in $X$ you have exactly $n+\sum_{v\in X}\lambda(v)$ vertices. but you know that $\lambda(v)\leq 2n$ thus you get: \begin{align} |Z| &=n+\sum_{v\in X}\lambda(v) \\ & \leq n+\sum_{v\in X}2n = n+n2n = 2n^2+n \end{align}

Answer 2

My interpretation:

The Confusion arises, here-

Assume that both $X$ and $X'$ have $n$ vertices. We plan to code the graph labels as suitable subgraphs which we attach to the vertices of $X$ and of $X'$. In time polynomial in the length of the input we can rename the labels and may assume, therefore, that $L = \{1 ..... k\}$ is the set of labels assigned by $\lambda$ and $\mu$. Note that $k\leq2n$ .

One needs to note that-

we can rename the labels and may assume, therefore, that $L = \{1 ..... k\}$ is the set of labels

assigned by $\lambda$ and $\mu$.

So, if you have $k\leq n$, then there is a guarantee or certainty,that there exists an Isomorphism from $X$ to $X'$ already, since, if $k\leq n$ then it is certain that $\exists i,j$ such that $ \lambda(v_i)=r=\mu(v_j)$ where $ 1\leq i,j \leq n$.

But if $k\leq 2n$, then $\lambda(v_i)$ may take $n$ different label, and $\mu(v_j)$ may take $n$ different label.

For example, consider Cyclic Graph $C_4$ and Complete Graph $K_4$. Add 1 vertex to 1st,2 vertices to 2nd,3 vertices to 3rd, 4 vertices to 4th vertex of $C_4$ and $K_4$ and rename them as $C'_4$ and $K'_4$. Now you have to use 14 different labels in $C'_4$, and none of them can be used in $K'_4$. Note that the number of vertices is same in both $C'_4$ and $K'_4$. Here, $|L|=2n=28$;

So, $k\leq2n$.