Total irredundance in graphs
type: Item
instance of: scholarly article
title: Total irredundance in graphs
zbMATH Open document ID: 1007.05074
DOI: 10.1016/S0012-365X(00)00459-3
author: Teresa W. Haynes
author: Stephen T. Hedetniemi
author: Michael A. Henning
author: Debra J. Knisley
author: Odile Favaron
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: A set \(S\) of vertices in a graph \(G\) is called a total irredundant set, if for each vertex \(v\) in \(G\) either \(v\) or one of its neighbours has no neighbour in \(S\setminus \{ v\}\). The authors study the minimum cardinality \(\text{ir}_t(G)\) and the maximum cardinality \(\text{IR}_t(G)\) of maximal irredundant sets in \(G\). They determine \(\text{ir}_t\) and \(\text{IR}_t\) for several special graphs, characterize the graphs \(G\) with \(\text{ir}_T(G)=0\) in terms of neighbourhood conditions and prove some lower bounds on \(\text{ir}_T\) for regular graphs. Furthermore, they characterize the trees \(T\) with \(\text{ir}_t(T)=1\) and prove some simple upper bounds on \(\text{ir}_T\) and \(\text{IR}_T\). The paper closes with a series of open problems.
reviewed by: Dieter Rautenbach
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 1838914
zbMATH Keywords: total irredundance
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00459-3
OpenAlex ID: W1992868998
description: scientific article; zbMATH DE number 1838914