The minimum rank problem for chordal graphs

Determining the minimum rank of a graph has been actively studied in combinatorial matrix theory over the past decade. Given a simple, undirected graph G on n
vertices, the problem is to determine the minimum rank over all real, symmetric
n x n matrices whose nonzero off-diagonal entries occur in the positions corresponding to the edges of G. We use graph decompositions such as cliques, cycles, complete bipartites, etc. to help determine the minimum rank. Our focus rests on decompositions using cliques and clique-stars. We note that cliques and clique-stars have minimum rank of 1 and 2 respectively. Such a decomposition is useful for the set of chordal graphs. A chordal graph is one that does not have an induced k-cycle, k ≥ 4. We use cliques and clique-stars to determine the minimum rank of chordal graphs with either three cliques or one clique and one clique-star in a decomposition. We highlight an example that demonstrates the difficulty of calculating the minimum rank.