On the rank of a matrix associated with a graph.
type: Item
instance of: scholarly article
title: On the rank of a matrix associated with a graph.
zbMATH Open document ID: 1047.05028
DOI: 10.1016/S0012-365X(03)00308-X
author: Vladimir Dobrynin
published in: Discrete Mathematics
publication date: 2004-02-14T00:00:00Z
review text: Let \(X\) be a real symmetric matrix indexed by the vertices of a graph \(G\) such that all its diagonal entries are \(1\), \(X_{ij}= 0\) whenever vertices \(i\), \(j\) are non-adjacent and \(| X_{ij}|\leq 1\) for all other entries of \(X\). Let \(r(G)\) be the minimum possible rank of the matrix \(X\). The author studies relations between \(r(G)\) and several other graph invariants including the independence number, the chromatic number of the complement, the Lovász theta function and the Colin de Verdière number.
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 2041903
zbMATH Keywords: Matrix associated with graph
zbMATH Keywords: Minimum rank
Wikidata QID: Q57772799
reviewed by: Dragoš Cvetković
MaRDI profile type: Publication
cites work: Sur la multiplicité de la première valeur propre non nulle du Laplacien. (On the multiplicity of the first nonzero eigenvalue of the Laplacian)
cites work: On the graph chromatic number and the rank of a matrix associated with the graph
cites work: On the function ``sandwiched'' between \(\alpha(G)\) and \(\bar\chi (G)\)
cites work: On the functions with values in \([\alpha (G), \overline{\chi} (G)]\)
cites work: Rank and chromatic number of a graph
cites work: The rank and size of graphs
cites work: The Colin de Verdière number and sphere representations of a graph
cites work: On the Shannon capacity of a graph
DBLP publication ID: journals/dm/Dobrynin04
description: scientific article; zbMATH DE number 2041903