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.

Original languageEnglish
Article numberR19
Pages (from-to)1-3
Number of pages3
JournalElectronic Journal of Combinatorics
Volume4
Issue number1 R
StatePublished - 1 Dec 1997

    Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics

ID: 36370343