Faculdade

Investigação

Graphs and minimum rank of matrices

TítuloGraphs and minimum rank of matrices
Publication TypeUnpublished
Year of Publication2006
AuthorsFernandes R, Perdigão C
Series TitlePreprint
AbstractFor a given connected (undirected) graph G, the minimum rank of G = (V(G), E(G)) is defined to be the smallest possible rank over all hermitian matrices A whose (i,j)th entry is non-zero whenever i≠j and {i,j} is an edge in G ({i,j} ε E(G)). For each vertex x in G ( x ε E(G)), Γ(x) is the set of all neighbors of x. Let R be the equivalence relation on (V(G) such that For all x,y ε V (G) xRy iff Γ(x) = Γ(y) Our aim is to define connected graphs G = ( V (G), E(G)) such that the minimum rank of G is equal to the number of equivalence classes for the relation R on V(G).
URLhttp://www.dm.fct.unl.pt/sites/www.dm.fct.unl.pt/files/preprints/2006/15_06.pdf