05C50 Online Seminar: Irene Sciriha
- Date: 02/24/2023
- Time: 08:00
University of Manitoba
Walks Reveal Important Graph Substructures
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.
The slides and a recording of this talk will be posted on the original website.
Stephen Kirkland, University of Manitoba
Hermie Monterde, University of Manitoba
The 05C50 Online is an international seminar about graphs and matrices held twice a month on Fridays.
Time: 8AM Pacific/10AM Central
For more information, visit https://sites.google.com/view/05c50online/home.
If you would like to attend, please register using this form to receive the zoom links: https://docs.google.com/forms/d/e/1FAIpQLSdQ98fh58cgeSWzbFe3t77i28FXDck1gYuX9jv_qd4kEf5l_Q/viewform?usp=sf_link