On Order and Rank of Graphs

Details On Order and Rank of Graphs On Order and Rank of Graphs

2012-01-15

arxiv.org/abs/1201.3060v1

Mathematics

Combinatorics

13 pages

Scientific paper

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. Akbari, Cameron, and Khosrovshahi conjectured that the number of vertices of every reduced graph of rank r is at most m(r)=2^{(r+2)/2}-2 if r is even and m(r) = 5*2^{(r-3)/2}-2 if r is odd. In this article, we prove that if the conjecture is not true, then there would be a counterexample of rank at most 46. We also show that every reduced graph of rank r has at most 8m(r)+14 vertices.

Affiliated with

Also associated with

No associations

Rating

On Order and Rank of Graphs 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 Order and Rank of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Order and Rank of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-159058