Department of Mathematics

Combinatorics and Graph Theory

  •  Tree Cover Number and Maximum Semidefinite Nullity of Graphs Part 1
  •  11/21/2017
  •  4:10 PM - 5:00 PM
  •  C304 Wells Hall
  •  Rachel Domagalski, Michigan State University

For a given multigraph G, we can associate a complex Hermitian matrix A=[a_{ij}] as follows: a_{ij}=0 if i, j are distinct and v_i,v_j are nonadjacent, a_{ij} is nonzero if i, j are distinct and v_i,v_j are ends of a single edge, a_{ij} is a complex number if i=j or if v_i,v_j are joined by parallel edges. In this talk we consider the collection of positive semidefinite complex Hermitian matrices associated with a given multigraph G, denoted S_+(G). The minimum rank of A in S_+(G) is called the minimum semidefinite rank, denoted mr_+(G). The corresponding maximum semidefinite nullity, denoted by M_+(G), satisfies mr_+(G) + M_+(G)=|G| where |G| is the number of vertices in G. In order to compute M_+(G) for a given graph G, certain graph parameters have been developed. One such graph parameter is called the tree cover number of G, denoted T(G). This is the minimum number of vertex disjoint simple trees occurring as induced subgraphs of G that cover all vertices of G. This parameter is easier to compute than M_+(G). Also, it has been conjectured that for any multigraph G, T(G) <= M_+(G). In this talk, I will build the background knowledge to understanding the maximum semidefinite nullity of a graph and the tree cover number parameter.



Department of Mathematics
Michigan State University
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science