On the product of upper irredundance numbers of a graph and its complement
type: Item
instance of: scholarly article
title: On the product of upper irredundance numbers of a graph and its complement
zbMATH Open document ID: 0672.05049
DOI: 10.1016/0012-365X(89)90304-X
author: E. J. Cockayne
author: Christina M. Mynhardt
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4099348
zbMATH Keywords: complement of a graph
zbMATH Keywords: closed neighbourhood
zbMATH Keywords: irredundance number
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
cites work: Q5183522
cites work: Contributions to the theory of domination, independence and irredundance in graphs
cites work: Properties of Hereditary Hypergraphs and Middle Graphs
cites work: Q3791195
cites work: Q5632603
cites work: On Complementary Graphs
full work available at URL: 0012-365x(89)90304-x
OpenAlex ID: W2060612181
description: scientific article; zbMATH DE number 4099348