On the product of upper irredundance numbers of a graph and its complement (Q1119604)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the product of upper irredundance numbers of a graph and its complement |
scientific article |
Statements
On the product of upper irredundance numbers of a graph and its complement (English)
0 references
1989
0 references
A closed neighbourhood of a vertex x of a graph G is the set consisting of x and of all vertices which are adjacent to x in G. A vertex x is redundant in a subset X of the vertex set of G, if the closed neighbourhood of x is a subset of the union of closed neighbourhoods of all vertices of \(X=\{x\}\). If X contains no vertex redundant in X, then X is called irredundant. The upper irredundance number \({\mathbb{R}}(G)\) of G is the maximum number of vertices of an irredundant set in G. The paper studies the upper irredundance numbers of a graph G and of its complement \(\bar G.\) The Nordhaus-Gaddum type inequalities \({\mathbb{R}}(G)\). \({\mathbb{R}}(\bar G)\leq \lceil (p^ 2+2p)/4\rceil,\) \({\mathbb{R}}(G)+{\mathbb{R}}(\bar G)\leq p+1,\) where p is the number of vertices of G, are proved.
0 references
complement of a graph
0 references
closed neighbourhood
0 references
irredundance number
0 references