On the minimum rank of a graph over finite fields

2010/06/04 by Friedland, Shmuel, Loewy, Raphael · 1 citation
#05AC50 #11T99 #15A03 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1006.0770

Abstract

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 \FF_q with q elements, which is denoted by \mr(\FF_q,G). In the first part of this paper we show that the average minimum rank of simple undirected labeled graphs on n vertices over \FF₂ is (1-ε_n)n, were lim_n→∞ ε_n=0. In the second part of this paper we assume that G contains a clique K_k on k-vertices. We show that if q is not a prime then \mr(\FF_q,G)≤ n-k+1 for 4≤ k≤ n-1 and n≥ 5. It is known that \mr(\FF_q,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(\FF₃,G)>3. For k=n-3, n≥ 5 and q≥ 4 we show that \mr(\FF_q,G)≤ 4.

Cited by

• The rank distribution of matrices representing graphs with a long induced path over the field of two elements

Related

• The minimum rank problem over finite fields
• The minimum rank problem over the finite field of order 2: minimum rank 3
• On Minrank and Forbidden Subgraphs
• Variants on the minimum rank problem: A survey II
• The Minrank of Random Graphs over Arbitrary Fields