Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4603342 | Linear Algebra and its Applications | 2007 | 10 Pages |
Abstract
For a given connected (undirected) graph G , the minimum rank of G=(V(G),E(G))G=(V(G),E(G)) is defined to be the smallest possible rank over all hermitian matrices A whose (i,j)(i,j)th entry is non-zero if and only if i≠ji≠j and {i,j}{i,j} is an edge in G ({i,j}∈E(G){i,j}∈E(G)). For each vertex x in G (x∈V(G)x∈V(G)), N(x)N(x) is the set of all neighbors of x. Let R be the equivalence relation on V(G)V(G) such that∀x,y∈V(G)xRy⇔N(x)=N(y).Our aim is find classes of connected graphs G=(V(G),E(G))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)V(G).
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Rosàrio Fernandes, Cecı´lia Perdigão,