Graphs with large disjunctive total domination number - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2015

Graphs with large disjunctive total domination number

Résumé

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, γdt(G), is the minimum cardinality of such a set. We observe that γdt(G) ≤γt(G). Let G be a connected graph on n vertices with minimum degree δ. It is known [J. Graph Theory 35 (2000), 21 13;45] that if δ≥2 and n ≥11, then γt(G) ≤4n/7. Further [J. Graph Theory 46 (2004), 207 13;210] if δ≥3, then γt(G) ≤n/2. We prove that if δ≥2 and n ≥8, then γdt(G) ≤n/2 and we characterize the extremal graphs.
Fichier principal
Vignette du fichier
dmtcs-17-1-17.pdf (394.52 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01196847 , version 1 (10-09-2015)

Identifiants

Citer

Michael A. Henning, Viroshan Naicker. Graphs with large disjunctive total domination number. Discrete Mathematics and Theoretical Computer Science, 2015, Vol. 17 no. 1 (1), pp.255--281. ⟨10.46298/dmtcs.2104⟩. ⟨hal-01196847⟩

Collections

TDS-MACS
47 Consultations
1136 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More