On the maximum positive semi-definite nullity and the cycle matroid of graphs

Main Article Content

Hein van der Holst

Abstract

Let G = (V,E) be a graph with V = {1, 2, . . . ,n}, in which we allow parallel edges but no loops, and let S+(G) be the set of all positive semi-definite n x n matrices A = [ai,j] with ai,j = 0 if i ≠ j and i and j are non-adjacent, ai,j ≠ 0 if i ≠ j and i and j are connected by exactly one edge, and ai,j ∈ R if i = j or i and j are connected by parallel edges. The maximum positive semi-definite nullity of G, denoted by M+(G), is the maximum nullity attained by any matrix A ∈ S+(G). A k-separation of G is a pair of subgraphs (G1,G2) such that V (G1) ∪ V (G2) = V , E(G1) ∪ E(G2) = E, E(G1) ∩ E(G2) = ∅ and |V (G1) ∩ V (G2)| = k. When G has a k-separation (G1,G2) with k ≤ 2, we give a formula for the maximum positive semi-definite nullity of G in terms of G1,G2, and in case of k = 2, also two other specified graphs. For a graph G, let cG denote the number of components in G. As a corollary of the result on k-separations with k ≤ 2, we obtain that M+(G) − cG = M+(G') − cG' for graphs G and G' that have isomorphic cycle matroids.

Article Details

Section
Article