Bujtás, Csilla and Jaskó, Szilárd (2018) Bounds on the 2-domination number. DISCRETE APPLIED MATHEMATICS, 242 (19). pp. 4-15. ISSN 0166-218X
|
Text
1612.08301v1.pdf Download (207kB) | Preview |
Abstract
In a graph G, a set D⊆V(G) is called 2-dominating set if each vertex not in D has at least two neighbors in D. The 2-domination number γ2(G) is the minimum cardinality of such a set D. We give a method for the construction of 2-dominating sets, which also yields upper bounds on the 2-domination number in terms of the number of vertices, if the minimum degree δ(G) is fixed. These improve the best earlier bounds for any 6≤δ(G)≤21. In particular, we prove that γ2(G) is strictly smaller than n/2, if δ(G)≥6. Our proof technique uses a weight-assignment to the vertices where the weights are changed during the procedure. © 2017 Elsevier B.V.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Mathematical techniques; Graph theory; Dominating set; Dominating sets; Upper Bound; Cardinalities; Graph G; Combinatorial mathematics; Minimum degree; Weight assignment; k-domination; 2-domination; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA71 Number theory / számelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 17 Jan 2019 08:12 |
| Last Modified: | 17 Jan 2019 08:12 |
| URI: | http://real.mtak.hu/id/eprint/90073 |
Actions (login required)
 |
Edit Item |
