On the Colin de Verdière numbers of Cartesian graph products |
| |
Authors: | Felix Goldberg |
| |
Institution: | Department of Mathematics, Technion-IIT, Haifa 32000, Israel |
| |
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. |
| |
Keywords: | 05C50 05C83 |
本文献已被 ScienceDirect 等数据库收录! |
|