| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4602281 | Linear Algebra and its Applications | 2009 | 6 Pages |
Abstract
Let G be a connected graph with Colin de Verdière number μ(G). We study the behaviour of μ with respect to the Cartesian product of graphs. We conjecture that if G=G1□G2, with G1,G2 connected, then μ(G)⩾μ(G1)+μ(G2) and prove that μ(G)⩾μ(G1)+h(G2)-1, where h is the Hadwiger number (i.e. the order of the largest clique minor). In addition we provide an explicit construction of a Colin de Verdière matrix with corank μ(G1)+μ(Kn) for the graph G=G1□Kn.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
