The minimum rank problem over finite fields

2008/01/18 by Jason Grout, Grout, Jason · 1 citation
Computer Science · Mathematics · #05B25 #05C50 #05C75 #15A03 #51E20 #Advanced Graph Theory Research #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research

paper · pdf · doi:10.48550/arxiv.0801.2987

openalex publication_date 2008/01/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The structure of all graphs having minimum rank at most k over a finite field with q elements is characterized for any possible k and q. A strong connection between this characterization and polarities of projective geometries is explained. Using this connection, a few results in the minimum rank problem are derived by applying some known results from projective geometry.

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 the finite field of order 2: minimum rank 3
• On the minimum rank of a graph over finite fields
• The Minimum Rank Problem: a counterexample
• Variants on the minimum rank problem: A survey II
• An exact algorithm for the minimum rank of a graph