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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
S. Akbari, P. J. Cameron and G. B. Khosrovshahi: Ranks and signatures of adjacency matrices, unpublished manuscript.
N. Alon and P. D. Seymour: A counterexample to the rank-coloring conjecture, J. Graph Theory 13 (1989), 523–525.
T. Ericson and V. Zinoviev: Codes on Euclidean Spheres, North-Holland Mathematical Library, 63, North-Holland Publishing Co., Amsterdam, 2001.
E. Ghorbani, A. Mohammadian and B. Tayfeh-Rezaie: Maximum order of trees and bipartite graphs with a given rank, Discrete Math. 312 (2012), 3498–3501.
E. Ghorbani, A. Mohammadian and B. Tayfeh-Rezaie: Maximum order of triangle-free graphs with a given rank, J. Graph Theory, in press
C.D. Godsil and G. F. Royle: Chromatic number and the 2-rank of a graph, J. Combin. Theory Ser. B 81 (2001), 142–149.
W.H. Haemers and M. J. P. Peeters: The maximum order of adjacency matrices of graphs with a given rank, Designs, Codes and Cryptography 65 (2012), 223–232.
A. Kotlov: Rank and chromatic number of a graph, J. Graph Theory 26 (1997), 1–8.
A. Kotlov and L. Lovász: The rank and size of graphs, J. Graph Theory 23 (1996), 185–189.
L. Lovász and M. Saks: Lattices, Möbius functions and communication complexity, in: Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, 81–90.
L. Lovász and M. Saks: Communication complexity and combinatorial lattice theory, J. Comput. System Sci. 47 (1993), 322–349.
N. Nisan and A. Wigderson: On rank vs. communication complexity, Combinatorica 15 (1995), 557–565.
C. van Nuffelen: A bound for the chromatic number of a graph, Amer. Math. Monthly 83 (1976), 265–266.
R. A. Rankin: The closest packing of spherical caps in n dimensions, Proc. Glasgow Math. Assoc. 2 (1955), 139–144.
A. A. Razborov: The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear, Discrete Math. 108 (1992), 393–396.
G. F. Royle: The rank of a cograph, Electron. J. Combin. 10 (2003).
C. Zong: Sphere Packings, Springer-Verlag, New York, 1999.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ghorbani, E., Mohammadian, A. & Tayfeh-Rezaie, B. On order and rank of graphs. Combinatorica 35, 655–668 (2015). https://doi.org/10.1007/s00493-015-2922-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-015-2922-4