REAL

Bounds on the 2-domination number

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

[img]
Preview
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 Edit Item