Upper minus domination in regular graphs (Q1567668): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
 
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(99)00245-9 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1975586942 / rank
 
Normal rank

Latest revision as of 11:00, 30 July 2024

scientific article
Language Label Description Also known as
English
Upper minus domination in regular graphs
scientific article

    Statements

    Upper minus domination in regular graphs (English)
    0 references
    19 November 2000
    0 references
    A minus dominating function of a graph \(G\) is a function \(f: V(G)\to \{-1,0,1\}\) such that the sum of its values over the closed neighbourhood \(N[v]\) of any vertex \(v\) of \(G\) is at least \(1\). (The closed neighbourhood \(N[v]\) is the set consisting of \(v\) and of all vertices adjacent to \(v\) in \(G\).) A minus dominating function \(f\) of \(G\) is minimal, if for any minus dominating function \(g\) of \(G\) the inequalities \(g(x)\leq f(x)\) for all \(x\in V(G)\) imply \(g= f\). The symbol \(f(V(G))\) denotes \(\sum_{x\in V(G)} f(x)\). The maximum value of \(f(V(G))\) taken over all minimal minus dominating functions \(f\) of \(G\) is the upper minus domination number \(\Gamma^-(G)\) of \(G\). The main result states that if \(G\) has \(n\) vertices and is regular of degree \(r\), then \(\Gamma^-(G)\leq (r+ 1)n/(r+ 3)\) for even \(r\) and \(\Gamma^-(G)\leq (r^2+ 1)n/(r+ 1)\) for odd \(r\). At the end, \(\Gamma^-(G)\) is related to the upper signed domination number \(\Gamma_s(G)\), which is a similar numerical invariant of a graph.
    0 references
    minus dominating function
    0 references
    upper minus domination number
    0 references
    upper signed domination number
    0 references
    0 references
    0 references

    Identifiers