Lower Ramsey numbers for graphs

AbstractLet μ(G) denote the smallest number of vertices in a maximal clique of the graph G, while i(G) (the independent domination number of G) denotes the smallest number of vertices in a maximal independent (i.e. independent dominating) set of G. For given integers l and m, the lower Ramsey number s(l, m) originally defined in [4], is the largest integer p such that every graph G of order p has μ(G)⩽l or i(G)⩽m. We find an upper bound for s(l, m) which is better than the upper bound in [4] if l<⌊m/2⌋. Combining this upper bound with a lower bound determined in [3], the numbers s(1,m) are determined exactly