zbMATH — the first resource for mathematics

The rank and size of graphs. (English) Zbl 0858.05060
A graph is twin-free if it has no two vertices with precisely the same sets of neighbours. Theorem: Let \(G\) be a twin-free graph on \(n\) vertices, and let \(r\) be the rank of its adjacency matrix. Then \(n=O(2^{{r\over 2}})\) as \(r\to\infty\). Conversely, given a twin-free graph on \(2\cdot 2^{{r\over 2}}-1\) vertices, of rank \(r\), one can duplicate its vertices, and then join a new vertex by an edge to one vertex of each twin pair. The graph obtained is again twin-free, has \(2\cdot 2^{{r+2\over 2}}-1\) vertices, and has adjacency matrix of rank \(r+2\); thus the bound is “best possible”. One application is to bound the chromatic number.

05C35 Extremal problems in graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI