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##.(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Combinatorial algorithm

**Physics Forums | Science Articles, Homework Help, Discussion**