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 x n matrices A = [a(i,j)] with a(i,j) = 0 if i not equal j and i and j are non-adjacent, a(i,j) not equal 0 if i not equal j and i and j are connected by exactly one edge, and a(i,j) is an element of 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 is an element of S+(G). A k-separation of G is a pair of subgraphs (G(1), G(2)) such that V (G(1)) boolean OR V (G(2)) = V, E(G(1)) boolean OR E(G(2)) = E, E(G(1)) boolean AND E(G(2)) = empty set and vertical bar V (G(1)) boolean AND V (G(2))vertical bar = k. When G has a k-separation (G(1), G(2)) with k = 2, we give a formula for the maximum positive semi-definite nullity of G in terms of G(1), G(2), and in case of k <= 2, also two other specified graphs. For a graph G, let c(G) denote the number of components in G. As a corollary of the result on k-separations with k <= 2, we obtain that M+(G) - c(G) = M+(G') - c(G') for graphs G and G' that have isomorphic cycle matroids.