The algorithmic complexity of minus domination in graphs (Q1917346): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Set OpenAlex properties.
 
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0166-218x(95)00056-w / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2043805568 / rank
 
Normal rank

Latest revision as of 08:30, 30 July 2024

scientific article
Language Label Description Also known as
English
The algorithmic complexity of minus domination in graphs
scientific article

    Statements

    The algorithmic complexity of minus domination in graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    6 October 1996
    0 references
    A minus dominating function of a graph \(G\) with vertex set \(V\) is a function \(f : V \to \{- 1,0,1\}\) such that the sum of its values over any closed neighbourhood \(N [v]\) is at least one; the closed neighbourhood of a vertex \(v\) is the set \(N[v]\) consisting of \(v\) and of all vertices which are adjacent to \(v\). The weight of \(f\) is the sum of its values over \(V\). The minimum weight of a minus dominating function \(f\) of \(G\) is the minus domination number \(\gamma^- (G)\) of \(G\), the maximum weight of a minimal minus dominating function of \(G\) is the upper minus domination number \(\Gamma^- (G)\) of \(G\). The problem to determine whether \(\gamma^- (G) \leq j\) or \(\Gamma^- (G) \leq j\) for a given graph \(G\) and a given number \(j\) is proved to be NP-complete even when restricted to bipartite graphs or chordal graphs. A linear-time algorithm for finding a minimum minus dominating function in a tree is presented.
    0 references
    minus dominating function
    0 references
    weight
    0 references
    minus domination number
    0 references
    NP-complete
    0 references
    algorithm
    0 references
    tree
    0 references

    Identifiers