Colin De Verdière Graph Invariant
Colin de Verdière's invariant is a graph parameter \mu(G) for any Graph (discrete mathematics), graph ''G,'' introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators. Definition Let G=(V,E) be a simple graph with vertex set V=\. Then \mu(G) is the largest corank of any symmetric matrix M=(M_)\in\mathbb^ such that: * (M1) for all i,j with i\neq j: M_<0 if $\backslash \backslash in\; E$, and $M\_=0$ if $\backslash \backslash notin\; E$; * (M2) $M$ has exactly one negative eigenvalue, of multiplicity 1; * (M3) there is no nonzero matrix $X=(X\_)\backslash in\backslash mathbb^$ such that $MX=0$ and such that $X\_=0$ if either $i=j$ or $M\_\backslash neq\; 0$ hold.

Characterization of known graph families

Several well-known families of graphs can be characterized in terms of their Colin de Verdièr ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  

Graph (discrete Mathematics)
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a Set (mathematics), set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') and each of the related pairs of vertices is called an ''edge'' (also called ''link'' or ''line''). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person ''A'' can shake hands with a person ''B'' only if ''B'' also shakes hands with ''A''. In contrast, if an edge from a person ''A'' to a person ''B'' means that ''A'' owes money to ''B'', then this graph is directed, because owing mon ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]