1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.