| Speaker | Tuerker Biyikoglu |
| Title | Nodal Domains in Cographs |
We investigate eigenvectors of a graph Laplacian and their nodal domains. We consider the adjacency, Laplacian, and generalized Laplacian (a symmetric matrix with non-positive off-diagonal elements) of a graph. The generalized Laplacian is also called a discrete Schrödinger operator. We associate a graph with a real vector. A nodal domain of a vector is a connected component of the maximal induced subgraph of the associated graph on which the vector does not change sign. A nodal domain is also called sign graph. The discrete analogue of Courant's nodal domain theorem provides upper bounds on the number of nodal domains of an eigenvector depending on the location of the corresponding eigenvalue in the spectrum. This bound is not sharp in general. We consider the problem of finding minimal and maximal numbers of nodal domains for some graph classes.
We present the relationship between nodal domains and hyperplane arrangements.
We consider a generalized Laplacian of a tree. We characterize for a tree: the maximal number of the strong nodal domains of an eigenvector corresponding to the k-th eigenvalue. We give an O(n2) time algorithm finding an eigenvector with maximum number of the strong nodal domains, which corresponds to the k-th eigenvalue. We show that to find an eigenvector of the k-th eigenvalue, which has minimum number of the strong nodal domains, is NP-complete.
For the Laplacian matrix of a hypercube, we show that each eigenvalue except the largest one has an eigenvector with two weak nodal domains. We also show that the first half of the eigenvalues have an eigenvector with two strong nodal domains. We give a lower bound for the number of nodal domains of eigenvectors belonging to the second largest eigenvalue.
We consider the Laplacian matrix of a cograph. A graph is called cograph if it has no path with four vertices as an induced subgraph. We give an algorithm for finding the minimum or maximum number of nodal domains of a cograph in O(n2) time. Finally we prove the conjecture that the rank of the adjacency matrix of a cograph is equal to the number of distinct nonzero columns of the adjacency matrix.