Maximal irredundant functions Original Research Article

A real-valued function g : V → [0, 1] on the vertex set of a graph is irredundant if g(v) > 0 implies there exists a vertex w in the closed neighborhood of v, N[v], such that g(N[w]) = 1. Irredundant functions are a real-valued generalization of irredundant sets. In this paper we define a real-valued analog to the well-known graph parameter ir(G), and show how to compute it. We also provide a polynomial-time algorithm for recognizing maximal irredundant functions.