Research output: Contribution to journal › Article › peer-review
Let
B(G) = {X : X is an element of R-nxn, X = X-T, I less than or equal to X less than or equal to I + A(G)}
and
C(G) = {X : X is an element of R-nxn, X = X-T, I - A(G) less than or equal to X less than or equal to I + A(G)}
be classes of matrices associated with graph G. Here n is the number of vertices in graph G, and A( G) is the adjacency matrix of this graph. Denote r(G) = min(Xis an element ofc(G)) rank(X), r(+)(G) = min(Xis an element ofB(G)) rank(X). We have shown previously that for every graph G, alpha(G) less than or equal to r(+)(G) less than or equal to (χ) over bar (G) holds and alpha(G) = r(+)(G) implies alpha(G) = (χ) over bar (G). In this article we show that there is a graph G such that alpha(G) = r(G) but alpha(G) <(G). In the case when the graph G doesn't contain two chordless cycles C-4 with a common edge, the equality alpha(G) = r(G) implies alpha(G) = (χ) over bar (G). Corollary: the last statement holds for d(G) - the minimal dimension of the orthonormal representation of the graph G.
Original language | English |
---|---|
Article number | 5 |
Number of pages | 5 |
Journal | Electronic Journal of Combinatorics |
Volume | 11 |
Issue number | 1 |
State | Published - 22 Mar 2004 |
ID: 36371825