On the Colin de Verdiere graph number and penny graphs

2020/06/09 by Abdo Y. Alfakih, A. Y. Alfakih, Alfakih, A. Y.
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Metric Geometry (math.MG) #math.CO #math.MG

paper · pdf · doi:10.48550/arxiv.2006.05197

v1

arxiv created 2020/06/09 · openalex publication_date 2020/06/09 · arxiv updated 2020/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Colin de Verdiere number of graph G, denoted by μ(G), is a spectral invariant of G that is related to some of its topological properties. For example, μ(G) ≤ 3 iff G is planar. A penny graph is the contact graph of equal-radii disks with disjoint interiors in the plane. In this note we prove lower bounds on μ(G) when the complement G is a penny graph.

Related

• Three observations on the Colin de Verdière spectral graph parameter
• The Colin de Verdière number and graphs of polytopes
• A linear bound for the Colin de Verdière parameter μ for graphs embedded on surfaces
• The Weak Version of the Graph Complement Conjecture and Partial Results for the Delta Conjecture
• The Colin de Verdière Graph Parameter for Threshold Graphs