Upper minus domination in regular graphs (Q1567668): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:56, 5 March 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