On the minimum rank of a graph over finite fields

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

Raphael Loewy, S. Friedland

Publication date: 19 March 2012

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

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$.

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)

Cites Work

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

Cited In (7)

• The minimum rank problem over the finite field of order 2: Minimum rank 3
• The minimum rank problem over finite fields
• A note on universally optimal matrices and field independence of the minimum rank of a graph
• On the minimum vector rank of multigraphs
• On zero forcing number of graphs and their complements
• On the minimum semidefinite rank of a simple graph
• Subgraph complementation and minimum rank

Recommendations

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

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)