# Combinatorial algorithm

• secondprime
In summary, the matrix A can be divided into 4 sub matrices based on adjacency of vertex. The sub matrices are C, E, D, and B. The sub matrices are obtained by swapping any two rows (or columns) of the matrix C. Any change in the matrix C or D or both C and D changes the sub matrix E. The sub matrix E can be used to solve a problem that has been discussed before in this thread.

#### secondprime

Given a matrix A of a regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex ##x \in G##.

## A_x## is the symmetric matrix of the graph ##(G-x)##, where ##C## is the symmetric matrix of the graph created by vertices of ##(G-x)## which are adjacent to ##x## and ##D## is the symmetric matrix of the graph created by vertices of ##(G-x)## which are not adjacent to ##x##.

http://i.stack.imgur.com/qL2rD.jpg

## A_x = \left( \begin{array}{cc}

C & E \\

E^{T} & D\\

\end{array} \right) ##

It should be noted, that-

1. Interchanging/swapping any two rows (or columns) of ##C## does not affect matrix ##D## (and vice versa).

2. Any change in ##C## or ##D## or both ##C## and ##D## changes matrix ##E##.

**Problem:** If some vertices of ##G## is rearranged(i.e. permuted), ##A## will be different, say, this new matrix is ##B##. Again, matrix ##B## can be divided into 4 sub matrices based on adjacency of vertex ##x \in G## and ## B_x## can be obtained.

Assume-

1. ##C## is always a regular graph’s matrix and bigger than ##D##.

2. There exists an algorithm that always order ##D##(for a vertex ##x \in G##) takes ##K## times(assumed to be polynomial).

3. Each row of E has different permutation, i.e. , rows might have same number of 1's but there is no two rows which can be permuted to each other. Say, ##r_x , r_y## are two rows, there is no permutation ##\sigma## so that, ## \sigma r_x=\sigma r_y##. *So, there is no way ##E## to be a zero matrix or matrix of all 1's or a matrix has some identical rows.*

For ##n## vertices there will be total ##n## numbers of ##C,D##, each of them will take ##K##(assumed to be polynomial) time to sort. If Each ##C## takes ##f## time to sort, then the total complexity will be ##n\times K\times f##.

**according to above 3 assumptions, Does there exist a polynomial time algorithm to sort ##C## so that ##B=A##? i.e. Is there a polynomial##f## ?**

that discussion was incomplete and was the general case, this more specific. It would easier, if this thread is concluded.

Consider ##G## as a strongly ##k## regular graph G(srg(##n,k,\lambda ,\mu##);##\lambda ,\mu >0##).