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-


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

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.


closed as unclear what you're asking by Stefan Kohl, Chris Godsil, Alex Degtyarev, Yoav Kallus, Andrej Bauer Aug 29 '15 at 7:18

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 '15 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$ – Jim Aug 30 '15 at 7:40