On the minimum rank of a graph over finite fields

Details On the minimum rank of a graph over finite fields On the minimum rank of a graph over finite fields

2010-06-04

arxiv.org/abs/1006.0770v2

Mathematics

Combinatorics

16 pages

Scientific paper

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_2$ is $(1-\varepsilon_n)n$, were $\lim_{n\to\infty} \varepsilon_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)\le n-k+1$ for $4\le k\le n-1$ and $n\ge 5$. It is known that $\mr(\FF_q,G)\le 3$ for $k=n-2$, $n\ge 4$ and $q\ge 4$. We show that for $k=n-2$ and each $n\ge 10$ there exists a graph $G$ such that $\mr(\FF_3,G)>3$. For $k=n-3$, $n\ge 5$ and $q\ge 4$ we show that $\mr(\FF_q,G)\le 4$.

Affiliated with

Also associated with

No associations

Rating

On the minimum rank of a graph over finite fields does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the minimum rank of a graph over finite fields, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the minimum rank of a graph over finite fields will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-722423