On the Colin de Verdière numbers of Cartesian graph products

✍ Scribed by Felix Goldberg

• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 116 KB
• Volume: 431
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/j.laa.2008.11.014

✦ Synopsis

Colin de Verdière matrix Cartesian graph product Kronecker product of matrices

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

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 μ(G 1 ) + μ(K n ) for the graph G = G 1 K n .