×

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.

MSC:

05C99 Graph theory
05C05 Trees
05C38 Paths and cycles

Citations:

Zbl 0747.00036
PDFBibTeX XMLCite