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 limn→∞ε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.