# 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.

##### MSC:
 05C35 Extremal problems in graph theory 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
##### Keywords:
twin-free graph; adjacency matrix; chromatic number
Full Text: