Article ID Journal Published Year Pages File Type
4603342 Linear Algebra and its Applications 2007 10 Pages PDF
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).

Related Topics
Physical Sciences and Engineering Mathematics Algebra and Number Theory
Authors
, ,