05C50 Online Seminar: Irene Sciriha

  • Date: 02/24/2023
  • Time: 08:00
Lecturer(s):
Irene Sciriha, University of Malta
Location: 

University of Manitoba

Topic: 

Walks Reveal Important Graph Substructures

Description: 

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.

Organizers:

Stephen Kirkland, University of Manitoba 

Hermie Monterde, University of Manitoba

Other Information: 

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