Bujtás, Csilla and Jaskó, Szilárd (2018) Bounds on the 2domination number. DISCRETE APPLIED MATHEMATICS, 242 (19). pp. 415. ISSN 0166218X

Text
1612.08301v1.pdf Download (207kB)  Preview 
Abstract
In a graph G, a set D⊆V(G) is called 2dominating set if each vertex not in D has at least two neighbors in D. The 2domination number γ2(G) is the minimum cardinality of such a set D. We give a method for the construction of 2dominating sets, which also yields upper bounds on the 2domination 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 weightassignment 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; kdomination; 2domination; 
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 