Nodal Domain Theorems and Bipartite Subgraphs

2024/01/18 by Biyikoglu, Türker, Leydold, Josef, Stadler, Peter F.

paper · doi:10.57938/b1072f92-d08a-48d6-a908-3c717f8f9458

Abstract

The Discrete Nodal Domain Theorem states that an eigenfunction of the k-th largest eigenvalue of a generalized graph Laplacian has at most k (weak) nodal domains. We show that the number of strong nodal domains cannot exceed the size of a maximal induced bipartite subgraph and that this bound is sharp for generalized graph Laplacians. Similarly, the number of weak nodal domains is bounded by the size of a maximal bipartite minor. (author's abstract)

Related

• Graph Laplacians, Nodal Domains, and Hyperplane Arrangements
• Nodal domain theorem of signed hypergraphs
• Sharp lower bound on the "number of nodal decomposition" of graphs
• A nodal domain theorem and a higher-order Cheeger inequality for the graph p-Laplacian
• Nodal domain count for the generalized graph p-Laplacian