On the minimum rank of a graph over finite fields

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

Authors: S. Friedland, Raphael Loewy 

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

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

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 (14)

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

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)