Ramsey properties of generalised irredundant sets in graphs Original Research Article

For each vertex s of the subset S of vertices of a graph G, we define Boolean variables p,q,r which measure the existence of three kinds of S-private neighbours (S-pns) of s. A 3-variable Boolean function f=f(p,q,r) may be considered as a compound existence property of S-pns. The set S is called an f-set of G if f=1 for all s∈S and the class of all f-sets of G is denoted by Ωf. Special cases of Ωf include the independent sets, irredundant sets and CO-irredundant sets of G. For some f∈F it is possible to define analogues (involving f-sets) of the classical Ramsey graph numbers. We consider existence theorems for these f-Ramsey numbers and prove that some of them satisfy the well-known recurrence inequality which holds for the classical Ramsey numbers.