Combinatorial invariants for graph isomorphism problem

Details Combinatorial invariants for graph isomorphism problem Combinatorial invariants for graph isomorphism problem

2008-04-22

arxiv.org/abs/0804.3615v4

Computer Science

Computational Complexity

Scientific paper

Presented approach in polynomial time calculates large number of invariants for each vertex, which won't change with graph isomorphism and should fully determine the graph. For example numbers of closed paths of length k for given starting vertex, what can be though as the diagonal terms of k-th power of the adjacency matrix. For k=2 we would get degree of verities invariant, higher describes local topology deeper. Now if two graphs are isomorphic, they have the same set of such vectors of invariants - we can sort theses vectors lexicographically and compare them. If they agree, permutations from sorting allow to reconstruct the isomorphism. I'm presenting arguments that these invariants should fully determine the graph, but unfortunately I can't prove it in this moment. This approach can give hope, that maybe P=NP - instead of checking all instances, we should make arithmetics on these large numbers.

Affiliated with

Also associated with

No associations

Rating

Combinatorial invariants for graph isomorphism problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combinatorial invariants for graph isomorphism problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial invariants for graph isomorphism problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-104388