05C50 Online Seminar: Irene Sciriha

Non--isomorphic graphs with isomorphic canonical double cover (CDC) have the same number of walks of arbitrary length from corresponding vertices of the same degree. The total number of walks, for a specific length, depends only on the main eigensystem. What combinatorial properties do graphs with the same eigenspace have in common? A hierarchy of properties of classes of graphs is established in view of their CDCs, walk matrices, main eigenvalues, eigenvectors and eigenspaces. The main eigenspace of the adjacency matrix of a graph turns out to be the image of the walk matrix. This leads to a fixed parameter tractable algorithm that decides whether a graph is Hamiltonian, a problem that is NP hard and NP complete in general.