Graphs with large disjunctive total domination number

zbMATH Open1310.05159arXiv1409.1681MaRDI QIDQ5249240FDOQ5249240

Authors: Michael A. Henning, Viroshan Naicker 

Publication date: 30 April 2015

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, $gamm{a}_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, $gamm{a}_t^d(G)$, is the minimum cardinality of such a set. We observe that $gamm{a}_t^d(G)legamm{a}_t(G)$. Let $G$ be a connected graph on $n$ vertices with minimum degree $delta$. It is known [J. Graph Theory 35 (2000), 21--45] that if $deltage2$ and $nge11$, then $gamm{a}_t(G)le4n/7$. Further [J. Graph Theory 46 (2004), 207--210] if $deltage3$, then $gamm{a}_t(G)len/2$. We prove that if $deltage2$ and $nge8$, then $gamm{a}_t^d(G)len/2$ and we characterize the extremal graphs.

Full work available at URL: https://arxiv.org/abs/1409.1681

Recommendations

• Disjunctive total domination in graphs
• Disjunctive Total Domination Subdivision Number of Graphs
• Disjunctive domination in graphs with minimum degree at least two
• Bounds on the disjunctive total domination number of a tree
• The disjunctive bondage number and the disjunctive total bondage number of graphs

zbMATH Keywords

disjunctive total dominating settotal dominating set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (14)

• Disjunctive total domination in graphs
• Algorithmic aspects of paired disjunctive domination in graphs
• A constructive characterization of trees with equal total domination and disjunctive domination numbers
• Algorithmic aspects of \(b\)-disjunctive domination in graphs
• Analysis of Vulnerability of Some Transformation Networks
• Bounds on the disjunctive total domination number of a tree
• Disjunctive total domination stability in graphs
• B-disjunctive total domination in graphs: algorithm and hardness results
• Complexity and bounds for disjunctive total bondage
• Disjunctive domination in graphs with minimum degree at least two
• Algorithmic aspects of disjunctive total domination in graphs
• The disjunctive domination number of a graph
• Disjunctive total domination in permutation graphs
• On disjunctive domination in graphs

This page was built for publication: Graphs with large disjunctive total domination number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5249240)