Maximal irredundant functions
type: Item
instance of: scholarly article
title: Maximal irredundant functions
zbMATH Open document ID: 0858.05059
DOI: 10.1016/0166-218X(95)00071-X
author: Yanyan Li
published in: Discrete Applied Mathematics
publication date: 1997-03-23T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 933127
zbMATH Keywords: irredundance
zbMATH Keywords: closed neighbourhood
zbMATH Keywords: irredundance number
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: irredundant functions
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Fractional matchings and covers in infinite hypergraphs
cites work: Packing Problems and Hypergraph Theory: A Survey
cites work: Linear-time computation of optimal subgraphs of decomposable graphs
cites work: On the computational complexity of upper fractional domination
cites work: On the Fractional Covering Number of Hypergraphs
cites work: Properties of Hereditary Hypergraphs and Middle Graphs
cites work: Q5753985
cites work: Q3032297
cites work: Q3740231
cites work: Q3791195
cites work: Solving Polynomial Strict Inequalities Using Cylindrical Algebraic Decomposition
cites work: Q4739657
cites work: Fractional matchings and the Edmonds-Gallai theorem
full work available at URL: 0166-218x(95)00071-x
OpenAlex ID: W2089594258
Recommended article: Q3410863
Recommended article: Q2960958
Recommended article: Q3791195
Recommended article: Distance irredundance in graphs: Complexity issues
Recommended article: Q3139859
Recommended article: Q5461451
Recommended article: Q4028517
Recommended article: Q4346795
Recommended article: Irredundance and Maximum Degree in Graphs
Recommended article: Total irredundance in graphs
description: scientific article; zbMATH DE number 933127