Disjunctive total domination in graphs

DOI10.1007/S10878-014-9811-4MaRDI QIDQ266033zbMATH OpenOpenAlexFDO

Authors Michael A. Henning, Viroshan Naicker

Publication date 13 April 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

claw-free graphdisjunctive total dominating settotal dominating set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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 distance2 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)$. We prove that if $G$ is a connected graph of order$nge8$, then $gamm{a}_t^d(G)le2(n-1)/3$ and we characterize the extremal graphs. It is known that if $G$ is a connected claw-free graph of order$n$, then $gamm{a}_t(G)le2n/3$ and this upper bound is tight for arbitrarily large$n$. 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 order$n>10$, then $gamm{a}_t^d(G)le4n/7$ and we characterize the graphs achieving equality in this bound.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1529462 (Why is no real title available?)
• A survey of selected recent results on total domination in graphs
• Bounds on total domination in claw-free cubic graphs
• Claw-free graphs---a survey
• Fundamentals of resource allocation in wireless networks. Theory and algorithms
• Graphs with large total domination number
• On a conjecture on total domination in claw-free cubic graphs
• On a conjecture on total domination in claw-free cubic graphs: proof and new upper bound
• Paired-domination in claw-free cubic graphs
• The disjunctive domination number of a graph
• Total domination in claw-free graphs with minimum degree 2
• Total domination in graphs
• Total domination in graphs
• Upper total domination in claw‐free graphs

Cited in

(19)

• Disjunctive Total Domination Subdivision Number of Graphs
• scientific article; zbMATH DE number 5531984 (Why is no real title available?)
• 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
• Bounds on the disjunctive total domination number of a tree
• Analysis of Vulnerability of Some Transformation Networks
• Disjunctive total domination stability in graphs
• The disjunctive bondage number and the disjunctive total bondage number of graphs
• Porous exponential domination in Harary graphs
• B-disjunctive total domination in graphs: algorithm and hardness results
• Algorithmic aspects of disjunctive domination in graphs
• Complexity and bounds for disjunctive total bondage
• Graphs with large disjunctive total domination number
• Algorithmic aspects of disjunctive total domination in graphs
• The disjunctive domination number of a graph
• Domination versus disjunctive domination in trees
• Disjunctive total domination in permutation graphs
• On disjunctive domination in graphs

This page was built for publication: Disjunctive total domination in graphs

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