Given, a symmetric $n*n$ matrix $G$ with 0,1 entries. Each row of has same number of 1. $G$ is arranged in a certain order using a rule. The rule is described below-
$G$ is partitioned in to two sub matrices based on the adjacency of $n$ th column/row(column=row since it is a symmetric matrix).
e.g. n=10 for below matrix,10th vertex partitioned the whole matrix into 2 parts(matrices ),
Vertices which are adjacent to 10th vertex(7,8,9 in one part) and vertices which are not (1,2,3,4,5,6 in other part ).
After repetition, the final picture would be,
Question: If $H$ is a permuted $G$, (i.e. $H=P G$ ,where P is a permutation matrix), following the given rule, how many combinations require to check(minimum number) to ensure that H is a permuted G?
i.e if $H$ is not a permuted $G$,how many combinations require to check(minimum number) to ensure that H is not a permuted G?