Premium
The rank and size of graphs
Author(s) -
Kotlov Andrew,
Lovász László
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199610)23:2<185::aid-jgt9>3.0.co;2-p
Subject(s) - combinatorics , mathematics , pairwise comparison , rank (graph theory) , adjacency matrix , graph , upper and lower bounds , adjacency list , discrete mathematics , statistics , mathematical analysis
We show that the number of points with pairwise different sets of neighbors in a graph is O (2 r/2 ), where r is the rank of the adjacency matrix. We also give an example that achieves this bound. © 1996 John Wiley & Sons, Inc.