# Combinatorial algorithm

1. May 22, 2015

### 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$ ?**

2. May 23, 2015

### Drakkith

Staff Emeritus
3. May 24, 2015

### secondprime

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

4. May 24, 2015

### Staff: Mentor

5. May 26, 2015

### secondprime

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

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook