On the product of upper irredundance numbers of a graph and its complement (Q1119604): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Christina M. Mynhardt / rank | |||
Property / reviewed by | |||
Property / reviewed by: Bohdan Zelinka / rank | |||
Revision as of 12:01, 10 February 2024
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