Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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.
Язык оригинала | Английский |
---|---|
Номер статьи | 5 |
Число страниц | 5 |
Журнал | Electronic Journal of Combinatorics |
Том | 11 |
Номер выпуска | 1 |
Состояние | Опубликовано - 22 мар 2004 |
ID: 36371825