Variations of \(Y\)-dominating functions on graphs (Q941347)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Variations of \(Y\)-dominating functions on graphs
scientific article

    Statements

    Variations of \(Y\)-dominating functions on graphs (English)
    0 references
    0 references
    0 references
    4 September 2008
    0 references
    Let \(Y\) be a subset of real numbers. A \(Y\)-dominating function of a graph \(G=(V,E)\) is a function \(f:V\to Y\) such that \(\sum_{u\in N_G[v]}f(u)\geq 1\) for all vertices \(v\in V\), where \(N_G[v]=\{v\}\cup \{u\mid (u,v)\in E\}\). Let \(f(S)=\sum_{u\in S}f(u)\) for any subset \(S\) of \(V\) and let \(f(V)\) be the weight of \(f\). The \(Y\)-domination problem is to find a \(Y\)-dominating function of minimum weight for a graph \(G=(V,E)\). In this paper, we study the variations of \(Y\)-domination such as \(\{k\}\)-domination, \(k\)-tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the \(\{k\}\)-domination, \(k\)-tuple domination, signed domination, and minus domination numbers of paths, cycles, \(n\)-fans, \(n\)-wheels, \(n\)-pans, and \(n\)-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs.
    0 references
    dominating functions
    0 references
    \(k\)-tuple domination
    0 references
    \(\{k\}\)-domination
    0 references
    signed domination
    0 references
    minus domination
    0 references
    strongly chordal graphs
    0 references
    dually chordal graphs
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers