# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

# Discussiones Mathematicae Graph Theory

## GENERALISED IRREDUNDANCE IN GRAPHS: NORDHAUS-GADDUM BOUNDS

Ernest J. Cockayne and Stephen Finbow

University of Victoria
e-mail: cockayne@math.uvic.ca

## Abstract

For each vertex s of the vertex subset S of a simple graph G, we define Boolean variables p = p(s,S), q = q(s,S) and r = r(s,S) which measure 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 subset S is called an f-set of G if f = 1 for all s ∈ S and the class of f-sets of G is denoted by Ω f(G). Only 64 Boolean functions f can produce different classes Ω f(G), special cases of which include the independent sets, irredundant sets, open irredundant sets and CO-irredundant sets of G.

Let Qf(G) be the maximum cardinality of an f-set of G. For each of the 64 functions f, we establish sharp upper bounds for the sum Qf(G)+Qf( G) and the product Qf(G)Qf( G) in terms of n, the order of G.