TY - JOUR

T1 - On the rank of a matrix associated with a graph

AU - Dobrynin, Vladimir

PY - 2004/2/6

Y1 - 2004/2/6

N2 - Let X be a real symmetric matrix indexed by the vertices of a graph G such that all its diagonal entries are 1, Xij=0 whenever vertices i,j are non-adjacent and |Xij|≤1 for all other entries of X. Let r(G) be the minimum possible rank of the matrix X. Then α(G)≤r(G)≤χ̄(G). It is well known that there is no upper bound on χ̄(G) in terms of α(G). For every natural k≥2 there exists graph G such that α(G)=2 and χ̄(G)=k. So it is interesting to find out whether there is an upper bound on χ̄(G) in terms of r(G). It is proved here that r(G)=i iff d(G)=i for i≤3. Here d(G) is the minimum dimension of the orthonormal labellings of G. Hence, if r(G) ≤3 then χ̄(G)≤2r(G)-1.

AB - Let X be a real symmetric matrix indexed by the vertices of a graph G such that all its diagonal entries are 1, Xij=0 whenever vertices i,j are non-adjacent and |Xij|≤1 for all other entries of X. Let r(G) be the minimum possible rank of the matrix X. Then α(G)≤r(G)≤χ̄(G). It is well known that there is no upper bound on χ̄(G) in terms of α(G). For every natural k≥2 there exists graph G such that α(G)=2 and χ̄(G)=k. So it is interesting to find out whether there is an upper bound on χ̄(G) in terms of r(G). It is proved here that r(G)=i iff d(G)=i for i≤3. Here d(G) is the minimum dimension of the orthonormal labellings of G. Hence, if r(G) ≤3 then χ̄(G)≤2r(G)-1.

KW - Matrix associated with graph

KW - Minimum rank

UR - http://www.scopus.com/inward/record.url?scp=0347415780&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(03)00308-X

DO - 10.1016/S0012-365X(03)00308-X

M3 - Article

AN - SCOPUS:0347415780

VL - 276

SP - 169

EP - 175

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -