Dunbar, Jean; Laskar, Renu; Monroe, Ted Global irredundant sets in graphs. (English) Zbl 0765.05090 Combinatorics, graph theory, and computing, Proc. 22nd Southeast Conf., Baton Rouge/LA (USA) 1991, Congr. Numerantium 85, 65-72 (1991). Summary: [For the entire collection see Zbl 0747.00036.]Let \(S\) be a set of vertices in a graph \(G=(V,E)\). A vertex \(x\in S\) is \(S\)-irredundant (in \(G)\) if \(N[z]-N[S-\{x\}]\neq\varnothing\), where \(N[x]\), the closed neighborhood of vertex \(x\), equals the set of vertices adjacent to \(x\), including vertex \(x\) itself, and \(N[S]\) is the union of the closed neighborhoods of all vertices \(x\in S\). A set \(S\) of vertices is (i) irredundant in \(G\) if every vertex \(x\in S\) is \(S\)-irredundant in \(G\), (ii) global irredundant if every vertex \(x\in S\) is either \(S\)- irredundant in \(G\) or \(S\)-irredundant in \(G'\), the complement of \(G\), and (iii) universal irredundant if \(S\) is irredundant in \(G\) and \(G'\). The irredundance number, \(\text{IR}(G)\), the global irredundance number, \(\text{IR}_ g(G)\), and the universal irredundance number, \(\text{IR}_ u(G)\), equal the maximum cardinality of an irredundant set, a global irredundant set and a universal irredundant set, respectively. In this paper we examine these irredundance parameters of a graph and we present a sufficient condition for which \(\text{IR}(G)=\text{IR}_ g(G)\). Graphs satisfying this equality include trees and sufficiently large paths and cycles. Cited in 1 Document MSC: 05C99 Graph theory 05C05 Trees 05C38 Paths and cycles Keywords:global irredundant sets; neighborhood; irredundance number; global irredundance number; universal irredundance number; universal irredundant set; trees; large paths and cycles Citations:Zbl 0747.00036 PDFBibTeX XMLCite \textit{J. Dunbar} et al., in: Proceedings of the twenty-second southeastern conference on combinatorics, graph theory, and computing, held at Louisiana State University, Baton Rouge, LA, USA, February 10-15, 1991. Winnipeg: Utilitas Mathematica Publishing Inc.. 65--72 (1991; Zbl 0765.05090)