The Colin de Verdière Graph Parameter for Threshold Graphs

2006/12/22 by Hans Christianson, Christianson, Hans, Felix Goldberg +1
Computer Science · Mathematics · #05C50 #Combinatorics #Combinatorics (math.CO) #Computer science #Construct (python library) #Corollary #Discrete mathematics #Eigenvalues and eigenvectors #FOS: Mathematics #Graph #Graph theory and applications #Mathematics #Matrix (chemical analysis) #Matrix Theory and Algorithms #Physics #Spectral Theory in Mathematical Physics #math.CO #msc:05C50

paper · pdf · doi:10.48550/arxiv.math/0612720

19 pages, 1 figure. Added sharp result with F. Goldberg

openalex publication_date 2006/12/22 · arxiv created 2008/01/18 · arxiv updated 2011/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider Schrödinger operators on threshold graphs and prove a formula for the Colin de Verdière parameter in terms of the building sequence. We construct an optimal Colin de Verdière matrix for each connected threshold graph G of n vertices. For a large subclass of threshold graphs we construct an alternative Colin de Verdière matrix depending on a large parameter. As a corollary to this last construction, we give estimates on the size of the non-zero eigenvalues of this matrix.

Citations

• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs

Related

• The Colin de Verdière number and graphs of polytopes
• The minimum number of distinct eigenvalues of a threshold graph is at most 4
• More on Equienergetic Threshold Graphs
• Three observations on the Colin de Verdière spectral graph parameter
• Resolvent expansion for the Schrödinger operator on a graph with infinite rays