Maximal irredundant functions (Q1923617): Difference between revisions

The authors investigate a real-valued, so-called ``fractional'' analogue of the graph-theoretical property of irredundance (for which see, for example, the second author, \textit{R. Laskar} and \textit{J. Pfaff} [Irredundance in graphs: A survey, Congr. Numerantium 48, 183-193 (1985; Zbl 0647.05060)]). For a vertex \(v\) of a graph \(G=(V,E)\), the closed neighbourhood \(N[v]\) is the set consisting of \(v\) and all vertices adjacent to \(v\); for a subset \(S\subseteq V\), \(N(S)=\bigcup_{x\in S}N[x]\); \(S\) is irredundant if, for every \(v\in V\), \(N[v]-N[S-\{v\}]\neq\varnothing\). The irredundance number \(\text{ir}(G)\) is the minimum number of vertices in any maximal irredundant subset \(S\subseteq V\). A real-valued function \(g:V\to[0,1]\) is irredundant if \(g(v)>0\) implies the existence of a vertex \(w\in N[v]\) such that \(\sum_{x\in N[w]}g(x)=1\). From the authors' abstract: In this paper we define a real-valued analogue to \((\dots)\) \(\text{ir}(G)\), and show how to compute it. We also provide a polynomial-time algorithm for recognizing maximal irredundant functions.