TY - JOUR

T1 - ON THE FUNCTIONS WITH VALUES IN [Α(G), Χ̄(G)]

AU - Dobrynin, V.

AU - Pliskin, M.

AU - Prosolupov, E.

PY - 2004

Y1 - 2004

N2 - Let B(G) = {X : X ∈ ℝnxn, X = XT , I ≤ X ≤ I + A(G)} and C(G) = {X : X ∈ ℝnxn, X = XT , I - A(G) ≤ X ≤ 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) = minX∈C(G) rank(X), r +(G) = minX∈B(G) rank(X). We have shown previously that for every graph G, α(G) ≤ r+(G) ≤ χ̄(G) holds and α(G) = r+(G) implies α(G) = χ̄(G). In this article we show that there is a graph G such that α(G) = r(G) but α(G) <χ̄(G). In the case when the graph G doesn’t contain two chordless cycles C4 with a common edge, the equality α(G) = r(G) implies α(G) = χ̄(G). Corollary: the last statement holds for d(G) - the minimal dimension of the orthonormal representation of the graph G.

AB - Let B(G) = {X : X ∈ ℝnxn, X = XT , I ≤ X ≤ I + A(G)} and C(G) = {X : X ∈ ℝnxn, X = XT , I - A(G) ≤ X ≤ 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) = minX∈C(G) rank(X), r +(G) = minX∈B(G) rank(X). We have shown previously that for every graph G, α(G) ≤ r+(G) ≤ χ̄(G) holds and α(G) = r+(G) implies α(G) = χ̄(G). In this article we show that there is a graph G such that α(G) = r(G) but α(G) <χ̄(G). In the case when the graph G doesn’t contain two chordless cycles C4 with a common edge, the equality α(G) = r(G) implies α(G) = χ̄(G). Corollary: the last statement holds for d(G) - the minimal dimension of the orthonormal representation of the graph G.

M3 - Article

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

SN - 1097-1440

IS - 1 N

ER -