On the minimum rank of a graph over finite fields

In this paper we deal with two aspects of the minimum rank of a simple undirected graph G on n vertices over a finite field Fq with q elements, which is denoted by mr(Fq,G). In the first part of this paper we show that the average minimum rank of simple undirected labeled graphs on n vertices over F2 is (1-ε(n))n, were lim(n)→∞ε(n) = 0. In the second part of this paper we assume that G contains a clique Kk on k-vertices. We show that if q is not a prime then mr(Fq,G) ≤ n - k + 1 for 4 ≤ k ≤ n - 1 and n ≤ 5. It is known that mr(Fq,G) ≤ 3 for k = n - 2, n ≤ 4 and q ≤ 4. We show that for k = n - 2 and each n ≤ 10 there exists a graph G such that mr(F3,G) > 3. For k = n - 3, n ≤ 5 and q ≤ 4 we show that mr(Fq,G) ≥ 4.