Maximum order of triangle-free graphs with a given rank

E. Ghorbani, A. Mohammadian, B. Tayfeh-Rezaie

Published 2014-04-14Version 1

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. We determine the maximum order of reduced triangle-free graphs with a given rank and characterize all such graphs achieving the maximum order.