2014/10/01 by Michael A. Henning, Henning, Michael A., Viroshan Naicker +1
Computer Science · Mathematics · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1410.0187
openalex publication_date 2014/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 distance2 from it. The disjunctive total domination number, γdt(G), is the minimum cardinality of such a set. We observe that γdt(G) ≤ γt(G). We prove that if G is a connected graph of ordern ≥ 8, then γdt(G) ≤ 2(n-1)/3 and we characterize the extremal graphs. It is known that if G is a connected claw-free graph of ordern, then γt(G) ≤ 2n/3 and this upper bound is tight for arbitrarily largen. We show this upper bound can be improved significantly for the disjunctive total domination number. We show that if G is a connected claw-free graph of ordern > 10, then γdt(G) ≤ 4n/7 and we characterize the graphs achieving equality in this bound.