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

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 × 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 e 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 e 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) n E(G2) = f and |V (G1) n 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 +(¿) - c¿ for graphs G and ¿ that have isomorphic cycle matroids.