On the minimum rank of a graph over finite fields

DOI10.1016/J.LAA.2011.06.041zbMATH Open1241.05078OpenAlexW2962808515MaRDI QIDQ765180FDOQ765180

Authors S. Friedland, Raphael Loewy

Publication date 19 March 2012

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.0770

zbMATH Keywords

matrixcliquefinite fieldminimum rankscaled average minmum rank

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Finite fields and commutative rings (number-theoretic aspects) (11T99) Vector spaces, linear dependence, rank, lineability (15A03)

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 $F{F}_q$ with $q$ elements, which is denoted by $mr(F{F}_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 $F{F}_2$ is $(1-varepsilo{n}_n)n$, were $li{m}_{noinfty}varepsilo{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(F{F}_q,G)len-k+1$ for $4leklen-1$ and $nge5$. It is known that $mr(F{F}_q,G)le3$ for $k=n-2$, $nge4$ and $qge4$. We show that for $k=n-2$ and each $nge10$ there exists a graph $G$ such that $mr(F{F}_3,G)>3$. For $k=n-3$, $nge5$ and $qge4$ we show that $mr(F{F}_q,G)le4$.

Recommendations

• Graphs whose minimal rank is two: The finite fields case
• The minimum rank problem over finite fields
• On minimal rank over finite fields
• On the graph complement conjecture for minimum rank
• On the minimum semidefinite rank of a simple graph
• Minimum rank of graphs powers family
• The minrank of random graphs over arbitrary fields
• On minimum rank and zero forcing sets of a graph
• An upper bound for the minimum rank of a graph
• Bounds on minimum semidefinite rank of graphs

Cites work

• scientific article; zbMATH DE number 3904833 (Why is no real title available?)
• A characterization of tridiagonal matrices
• Expected values of parameters associated with the minimum rank of a graph
• Graphs whose minimal rank is two: The finite fields case
• On Fiedler's characterization of tridiagonal matrices over arbitrary fields
• Orthogonal Matrices Over Finite Fields
• Quadratic forms and the graph isomorphism problem
• The graphs for which the maximum multiplicity of an eigenvalue is two
• The minimum rank problem over the finite field of order 2: Minimum rank 3

Cited in

(14)

• The minrank of random graphs over arbitrary fields
• On minrank and forbidden subgraphs
• The minimum rank problem over finite fields
• On minrank and forbidden subgraphs
• Graphs whose minimal rank is two: The finite fields case
• On minimal rank over finite fields
• A note on universally optimal matrices and field independence of the minimum rank of a graph
• On zero forcing number of graphs and their complements
• The average cut-rank of graphs
• On the minimum vector rank of multigraphs
• On the minimum semidefinite rank of a simple graph
• Subgraph complementation and minimum rank
• Graphs whose minimal rank is two
• The minimum rank problem over the finite field of order 2: Minimum rank 3

This page was built for publication: On the minimum rank of a graph over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765180)