scientific article; zbMATH DE number 1303522

MaRDI QIDQ4250144zbMATH OpenFDO

Authors Hein van der Holst, László Lovász, Alexander Schrijver

Publication date 9 February 2000

zbMATH Keywords

\(\Delta Y\) transformationclique sumseigenvalueminor-monotoneplanaritystrong Arnold propertysubdivisionvector labellings

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

This paper surveys results on a spectral parameter of an undirected graph and gives proof techniques related to the parameter. The parameter was motivated by the study of maximum multiplicity of the second eigenvalue of certain Schrödinger operators. In addition to its background in differential geometry the parameter has nice graph-theoretic properties. Among other things, it is minor-monotone and can be used to characterize planarity of the graph. The survey is excellent and can serve as a good first step for the newcomer to the area. For the entire collection see [Zbl 0910.00036].

Recommendations

• The Colin de Verdière parameter, excluded minors, and the spectral radius
• Spectral graph theory and the inverse eigenvalue problem of a graph
• The Colin de Verdière number and sphere representations of a graph
• The extremal function and Colin de Verdière graph parameter

Cited in

(62)

• On the Colin de Verdière numbers of Cartesian graph products
• A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
• The extremal function and Colin de Verdière graph parameter
• Approximating the minimum rank of a graph via alternating projection
• Steinitz representations of polyhedra and the Colin de Verdière number
• Graphs with magnetic Schrödinger operators of low corank
• The inverse eigenvalue problem of a graph: multiplicities and minors
• Sign patterns of orthogonal matrices and the strong inner product property
• The Colin de Verdière parameter, excluded minors, and the spectral radius
• The Colin de Verdière number and joins of graphs
• Generalised outerplanar Turán numbers and maximum number of \(k\)-vertex subtrees
• An infinite family of linklessly embeddable Tutte-4-connected graphs
• Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
• Graph coloring and semidefinite rank
• A reduction procedure for the Colin de Verdière number of a graph
• Existence of a not necessarily symmetric matrix with given distinct eigenvalues and graph
• Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph
• Global rigidity of triangulations with braces
• Positive semidefinite matrix completion, universal rigidity and the strong Arnold property
• Graphs and obstructions in four dimensions.
• Phase transition of degeneracy in minor-closed families
• On vertex partitions and some minor-monotone graph parameters
• On Vertex Partitions and the Colin de Verdière Parameter
• Optimizing Colin de Verdière matrices of \(K_{4,4}\)
• On the graph complement conjecture for minimum rank
• Computing inertia sets using atoms
• Gershgorin disks for multiple eigenvalues of non-negative matrices
• Nullspace embeddings for outerplanar graphs
• Spectral graph theory and the inverse eigenvalue problem of a graph
• Tree densities in sparse graph classes
• The strong Arnold property for 4-connected flat graphs
• Colin de Verdière parameters of chordal graphs
• Computing the zero forcing number for generalized Petersen graphs
• On the number of edges in maximally linkless graphs
• Multiplicity of  the second‐largest eigenvalue of a planar graph
• The Colin de Verdière number and graphs of polytopes
• Constructions stemming from nonseparating planar graphs and their Colin de Verdière invariant
• New bounds on maximal linkless graphs
• Embedding and the rotational dimension of a graph containing a clique
• Eigenpolytope Universality and Graphical Designs
• Orthogonal realizations of random sign patterns and other applications of the SIPP
• Capturing polytopal symmetries by coloring the edge-graph
• On the Colin de Verdière number of graphs
• Graph coloring and semidefinite rank
• A linear bound for the Colin de Verdière parameter for graphs embedded on surfaces
• Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian
• On the Colin de Verdière graph number and penny graphs
• Improved bounds on the cop number when forbidding a minor
• The weak version of the graph complement conjecture and partial results for the delta conjecture
• Inverse eigenvalue problem for discrete Schrödinger operators of a graph
• Right-angled Artin groups and the cohomology basis graph
• Advances on similarity via transversal intersection of manifolds
• Even maps, the Colin de Verdière number and representations of graphs
• Orthogonal similarity via transversal intersection of manifolds
• Planarity criteria for metric graphs
• Clustered coloring of graphs excluding a subgraph and a minor
• Discrete quantitative nodal theorem
• Forbidden minors for the class of graphs G with (G) 2
• Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph
• Techniques for determining the minimum rank of a small graph
• Expected values of parameters associated with the minimum rank of a graph
• The minimum rank of symmetric matrices described by a graph: a survey

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4250144)