Title: The Full P-vertex problem- Recent Developments and Open Problems
Abstract: Vertex deletion is a fundamental operation in graph theory and network analysis, and understanding its effect on the spectrum of an associated matrix has been a longstanding problem in spectral graph theory. Originating in the work of Parter [3] (1960), this line of research led to the notion of a P-vertex, whose deletion increases the nullity of a symmetric matrix by one, the largest increase possible under vertex deletion.
For a simple graph G, let S(G) denote the family of all real symmetric matrices whose off-diagonal zero–nonzero pattern is prescribed by the edges of G. The full P-vertex problem asks for a characterization of graphs G for which there exists a nonsingular matrix A ∈ S(G) such that every vertex of G is a P-vertex. Equivalently, every principal submatrix of order n − 1 is singular with nullity one. Thus, the problem seeks graphs that admit a matrix realization in which every vertex is spectrally critical.
Although easy to state, the problem has proved to be surprisingly subtle. After the initial characterization of paths and stars [2], recent work [1] has established a complete characterization of unicyclic graphs with this property. Recent developments have revealed unexpected connections between the full P-vertex problem and perfect matchings.
This talk will provide an introduction to the full P-vertex problem, discuss its origins and motivations, survey the principal known results, and highlight recent developments and open problems.
References
[1] A. Howlader, P. Raickwade, and K. C. Sivakumar. The full P-vertex problem for unicyclic graphs. Linear Algebra and its Applications, 713:74–89, 2025.
[2] I.-J. Kim and B. L. Shader. Non-singular acyclic matrices. Linear and Multilinear Algebra, 57(4):399–407, 2009.
[3] S. Parter. On the eigenvalues and eigenvectors of a class of matrices. Journal of the Society for Industrial and Applied Mathematics, 8(2):376–388, 1960.