“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 13338 |
|
||||||
| Abstract: | |||||||
|
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.
Download TeX format |
|||||||
| back to top | |||||||
