scientific article; zbMATH DE number 1506495
A weak (strong) dominating set of a graph \(G=(V,E)\) is a subset \(D\) of the vertex set \(V\) such that every vertex in \(V\setminus D\) has a neighbour in \(D\) of smaller (larger) degree. The weak (strong) domination number \(\gamma_w(G)\) (\(\gamma_{st}(G)\)) of \(G\) is the minimum cardinality of a weak (strong) dominating set of \(G\) and the independent weak (strong) domination number \(i_w(G)\) (\(i_{st}(G)\)) of \(G\) is the minimum cardinality of an independent weak (strong) dominating set of \(G\). The authors prove tight upper bounds on the number of edges of graphs \(G\) with a given order and a given value of one of \(\gamma_w(G)\), \(\gamma_{st}(G)\), \(i_w(G)\) or \(i_{st}(G)\). Furthermore, they characterize all extremal graphs for their estimates. The given bounds differ considerably from Vizing's well-known bound on the number of edges of graphs with a given order and domination number and therefore capture the different characteristics of these recently defined domination parameters. If \(G\) is a graph of order \(n\) having \(m\) edges, then \[ \begin{alignedat}{2} m&\leq \tfrac{1}{2}(n-\gamma_w(G))(n+\gamma_w(G)-1), &\quad &m\leq \tfrac{1}{2}(n-i_w(G))(n+i_w(G)-1),\\ m&\leq \tfrac{1}{2}(n-\gamma_ {st}(G))(n-1)\text{ if }\gamma_{st}(G)\geq 3, &\quad &m\leq \tfrac{1}{2}(n-\gamma_ {st}(G))n \text{ if }\gamma_{st}(G)\leq 2\qquad \text{and}\\ m&\leq \tfrac{1}{2}(n-i_ {st}(G))n.\end{alignedat} \] {}.
- On strong and weak domination numbers in graphs
- On the number of edges in graphs with a given weakly connected domination number
- A note on a relation between the weak and strong domination numbers of a graph
- scientific article; zbMATH DE number 1229622
- Bounds on weak and strong total domination in graphs
- Maximum sizes of graphs with given domination parameters
- Relating the size of a connected graph to its total and restricted domination numbers
- On parameters related to strong and weak domination in graphs
- On the minimum number of bond-edge types and tile types: an approach by edge-colorings of graphs
- Special kinds of domination parameters of edge-deleted graphs.
- Weak and strong reinforcement number for a graph
- Inequalities between strong, weak domination numbers and chromatic number of a graph
- On strong (weak) independent sets and vertex coverings of a graph
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4504887)