“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 13338
School of Mathematics
  Title:   On order and rank of graphs
1.  E. Ghorbani
2.  A. Mohammadian
3.  B. Tayfeh-Rezaie
  Status:   Published
  Journal: Combinatorica
  Vol.:  35
  Year:  2015
  Pages:   655-668
  Supported by:  IPM
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
scroll left or right