A new function of a graph G is presented. Say that a matrix B that is indexed by vertices of G is feasible for G if it is real, symmetric and I ≤ B ≤ I + A(G), where I is the identity matrix and A(G) is the adjacency matrix of G. Let B(G) be the set of all feasible matrices for G, and let χ̄(G) be the smallest number of cliques that cover the vertices of G. We show that α(G) ≤ min{ rank(B) | B ∈ B(G)} ≤ χ̄(G) and that α(G) = min{ rank(B) | B ∈ B(G)} implies α(G) = χ̄(G). The well known Lovász number υ(G) of a graph G [1] is "sandwiched" between the size of the largest stable set in G and the smallest number of cliques that cover the vertices of G α(G) ≤ υ(G) ≤ χ̄(G). Some alternative definitions of υ(G) are introduced in [2] [3]. For example, υ(G) = max{ Λ(B) | B is a real positive semidefinite matrix indexed by vertices of G, Bvv = 1 for all v ∈ V (G), Buv = 0 whenever u - v in G}, where Λ(B) is the maximum eigenvalue of B, V (G) - the set of vertices of G, u - v denotes the adjacency of vertices u and v. Call the matrix B indexed by vertices of G feasible for G if B is real and symmetric, Bvv = 1 for all v ∈ V (G), Buv = 0 whenever u APL functional symbol slash bar v in G, 0 ≤ Buv ≤ 1 whenever u - v in G. Let B(G) be the set of all feasible matrices for G. Then [4] χ̄(G) = min{ rank(B) | B ∈ B(G), B = CT C, C ≥ 0}, where the inequality denotes componentwise inequality. The aim of this paper is to study a new function of graph G and α(Ḡ) < min{ rank(B) | B ∈ B(Ḡ)} by theorem.

Язык оригиналаанглийский
Номер статьиR19
Страницы (с-по)1-3
Число страниц3
ЖурналElectronic Journal of Combinatorics
Том4
Номер выпуска1 R
СостояниеОпубликовано - 1 дек 1997

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Геометрия и топология
  • Математика и теория расчета

ID: 36370343