Total irredundance in graphs (Q1849917): Difference between revisions

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.