Skip to Main content Skip to Navigation
Journal articles

Graphs with large disjunctive total domination number

Abstract : 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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01196847
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, September 10, 2015 - 3:17:08 PM
Last modification on : Friday, April 1, 2022 - 2:52:02 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:00:49 AM

File

dmtcs-17-1-17.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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

Share

Metrics

Record views

42

Files downloads

884