Odd Cycle Zero Forcing Parameters and the Minimum Rank of Graph Blowups

Abstract

The minimum rank problem for a simple graph G and a given field F is to determine the smallest possible rank among symmetric matrices over F whose i, j-entry, i â  j, is nonzero whenever i is adjacent to j, and zero otherwise; the diagonal entries can be any element in F. In contrast, loop graphs \mathscr{G} go one step further to restrict the diagonal i, i-entries as nonzero whenever i has a loop, and zero otherwise. When char F â  2, the odd cycle zero forcing number and the enhanced odd cycle zero forcing number are introduced as bounds for loop graphs and simple graphs, respectively. A relation between loop graphs and simple graphs through graph blowups is developed, so that the minimum rank problem of some families of simple graphs can be reduced to that of much smaller loop graphs.