### Friday, May 16, 2014 (1:00 p.m. in Yost 306)

**Title: **An Approach to Graph Isomorphism Using Spanning Trees Generated by Breadth First Search

**Speaker:** Alexey Ilchenko (Case Western Reserve University)

**Abstract: **Graph Isomorphism is a problem of determining whether or not a bijective function between

two graphs exists which also preserves the adjacency relation between nodes. If graphs,

regardless of how they are drawn or in what order the nodes are listed, are shown to be isomorphic,

then they are essentially the same. This has direct applications in fields even outside

of computer science and mathematics. This paper presents a novel way to determine whether

this relationship between any given unweighted and undirected graphs exists by employing

the invariant property of shortest distance which we exploit by generating a spanning tree

using Breadth First Search. The Algorithm heavily relies on guessing and backtracking, but

the number of guesses which are available to be made are heavily reduced from a naive approach.

The running times of the presented algorithm are measured by exploring some growth

parameters of random graphs. This Algorithm is presented as an algorithmic alternative to

previously known group theoretic approaches at solving the same problem. This paper may

be found at http://filer.case.edu/axi48/thesis/ while the supplementary code may be found at

https://github.com/ijkilchenko/GraphIsomorphism.