1
$\begingroup$

Context: I am studying Weisfeiler Lehman method(WL method) and have clear idea about 1 and 2 dimensional WL method. I was wondering about the individualization process described below-

Individualization:

$G$ is a $r$ regular graph . $n$ th vertex of $G$ is $v_n$. All vertices which are not adjacent to $ v_n $ create a sub-graph $C_1$. All vertices adjacent to $ v_n $ create a sub-graph $, C_2 $. A vertex of $C_2$ is $ v_{n-1}$.

Using same method , based on adjacency of $ v_{n-1}$, $C_2$ can be divided.

All vertices which are not adjacent to $ v_{n-1}$ create a sub-graph $C_3$.

All vertices adjacent to $ v_{n-1}$create a sub-graph $, C_4 $. In general , $ C_{2y} $ is a graph and can be divided/ partitioned in to 2 sub graphs $ C_{2y+1}, C_{2y+2} $ .

This method individualizes a set of $k$ vertices where $k< log_2(n)$.

Question:
Does above individualization exist in current literature ?

Initially, I thought , it is a variant of $k$ dim Wl method.

Motivation : Graph Isomorphism.

PS: Feel free to edit the post. let me know if it is still unclear.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It seems that the result of your individualization process depends very sensitively on the order in which vertices are listed, e.g., which vertex serves as $v_n$ to begin the process. Under these circumstances, I don't see the relevance of this to the graph isomorphism problem, and therefore I doubt that the process has been studied, unless it was for an entirely different purpose. $\endgroup$
    – Andreas Blass
    Aug 30, 2015 at 7:33
  • $\begingroup$ @AndreasBlass , Thanks for you comment, it was helpful. I was trying to use the above process for Graph Isomorphism testing with WL method. I have been asked where I got it. It is suspected, that the process exists which I have expressed \written in an elementary way. I 'believe' this process can help to improve the upper bound. $\endgroup$
    – Michael
    Aug 30, 2015 at 7:40

0

Reset to default