BSC4024104 Project Details

SupervisorDong Fengming
Project CodeBSC4024104
Title of ProjectTrees with some special eigenvalues
Description

For any graph G=(V,E), where V={vi:1≤i≤n}, the adjacency matrix of G with respect to the vertex ordering v1,v2,⋯,vn is defined to be the square matrix
A(G)=(ai,j)n×n, where
ai,j={1,if vivj∈E;0,otherwise.
The characteristic polynomial of G, denoted by PG(x), is defined to be det(xIn−A(G)), where In is the identical matrix of size n. The roots of PG(x) are called the eigenvalues of G.

A tree is a connected graph which has no cycles. Some trees T have an eigenvalue equal to 1 or −1. For example, for the two trees shown below,

 


their characteristic polynomials are


From the expression given above, both T1 and T2 have eigenvalues 1 and −1.

Are there other trees which have an eigenvalue equal to 1 or −1?

In this project, students will target to determine trees which have 1 or −1 as an eigenvalue.

 

Pre-requisites• Linear algebra, abstract algebra, combinatorial analysis, graph theory.
References[1] Cvetkovi´c, Dragos, Peter Rowlinson, and Slobodan Simi´c. “An introduction to the theory of graph spectra.” (No Title) (2009).
https://doi.org/10.1017/CBO9780511801518
[2] Hofmeister M. On the two largest eigenvalues of trees. Linear algebra and its applications 260 (1997), 43-59.
https://doi.org/10.1016/S0024-3795(97)80004-3
[3] Jones, Owen, “Spectra of simple graphs”. Whitman college 13 (2013): 1-20.
https://www.whitman.edu/documents/academics/majors/mathematics/Jones.pdf
[4] K.M. Koh, Fengming Dong and E.G. Tay, Introduction to graph theory: with solutions to selected problems, World Scientific, Singapore, 2023.
https://doi.org/10.1142/13637