A survey of selected recent results on total domination in graphs
From MaRDI portal
Publication:998491
DOI10.1016/j.disc.2007.12.044zbMath1219.05121OpenAlexW2006503776MaRDI QIDQ998491
Publication date: 28 January 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2007.12.044
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Total double Roman domination in graphs ⋮ Chromatic total domination in graphs ⋮ Integer linear programming formulations for double roman domination problem ⋮ COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS ⋮ Game total domination subdivision number of a graph ⋮ Total restrained bondage in graphs ⋮ The Disjunctive Bondage Number and the Disjunctive Total Bondage Number of Graphs ⋮ TOTAL DOMINATION POLYNOMIAL OF SOME GRAPHS ⋮ STRONG k-GEODETIC PROBLEM IN GRAPHS: COMPUTATIONAL COMPLEXITY AND SOME RESULTS ⋮ Partitioning claw-free subcubic graphs into two dominating sets ⋮ Simultaneously dominating all spanning trees of a graph ⋮ A Rough-Set Based Solution of the Total Domination Problem ⋮ On the total and strong version for Roman dominating functions in graphs ⋮ \( P_5\)-isolation in graphs ⋮ The total co-independent domination number of some graph operations ⋮ On the double total dominator chromatic number of graphs ⋮ Total Roman domination in the lexicographic product of graphs ⋮ A sharp upper bound on the cycle isolation number of graphs ⋮ On domatic and total domatic numbers of Cartesian products of graphs ⋮ A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ The restrained double Roman domination in graphs ⋮ Algorithmic Aspects of Disjunctive Total Domination in Graphs ⋮ On total domination and minimum maximal matchings in graphs ⋮ The geometric-arithmetic index of trees with a given total domination number ⋮ Total \(k\)-domination in Cartesian product of complete graphs ⋮ TOTAL DOMINATION INTEGRITY OF WHEEL RELATED GRAPHS ⋮ Algorithmic and complexity aspects of problems related to total restrained domination for graphs ⋮ Nordhaus-Gaddum bounds for total domination ⋮ Disjunctive total domination in permutation graphs ⋮ Unnamed Item ⋮ Relating the annihilation number and the total domination number for some graphs ⋮ Relating the total \(\{2\}\)-domination number with the total domination number of graphs ⋮ On matching and semitotal domination in graphs ⋮ Total and paired domination numbers of toroidal meshes ⋮ Bounds on neighborhood total domination in graphs ⋮ A note on improved upper bounds on the transversal number of hypergraphs ⋮ Efficient self-stabilizing algorithms for minimal total \(k\)-dominating sets in graphs ⋮ Equality in a linear Vizing-like relation that relates the size and total domination number of a graph ⋮ Bounds on the connected domination number of a graph ⋮ The algorithmic complexity of bondage and reinforcement problems in bipartite graphs ⋮ Semitotal domination in claw-free cubic graphs ⋮ A characterization of \(P_5\)-free, diameter-2-critical graphs ⋮ Semitotal domination in claw-free cubic graphs ⋮ Hardness results of global total \(k\)-domination problem in graphs ⋮ Relating ordinary and total domination in cubic graphs of large girth ⋮ On dominated coloring of graphs and some Nordhaus–Gaddum-type relations ⋮ Quasi-total Roman domination in graphs ⋮ On a conjecture of Murty and Simon on diameter 2-critical graphs ⋮ Integer linear programming models for the weighted total domination problem ⋮ A characterization of trees having a minimum vertex cover which is also a minimum total dominating set ⋮ b-Disjunctive Total Domination in Graphs: Algorithm and Hardness Results ⋮ 2-colorings in \(k\)-regular \(k\)-uniform hypergraphs ⋮ Lower bounds on the total domination number of a graph ⋮ An efficient algorithm for distance total domination in block graphs ⋮ A note on the \(k\)-tuple total domination number of a graph ⋮ NP-completeness results for partitioning a graph into total dominating sets ⋮ Counting dominating sets in generalized series-parallel graphs ⋮ Domination parameters in coronene torus network ⋮ Domination and Total Domination in Hypergraphs ⋮ Domination in Digraphs ⋮ Connected Domination ⋮ On the uniform domination number of a finite simple group ⋮ Closed formulas for the total Roman domination number of lexicographic product graphs ⋮ Relating the total domination number and the annihilation number of cactus graphs and block graphs ⋮ A characterization of graphs with disjoint total dominating sets ⋮ Total Roman reinforcement in graphs ⋮ Total $k$-Rainbow domination numbers in graphs ⋮ A constructive characterization of trees with equal total domination and disjunctive domination numbers ⋮ Total Roman {2}-domination in graphs ⋮ Outer-independent total Roman domination in graphs ⋮ Packing and domination parameters in digraphs ⋮ Semipaired domination in maximal outerplanar graphs ⋮ The total bondage numbers and efficient total dominations of vertex-transitive graphs ⋮ Disjoint paired-dominating sets in cubic graphs ⋮ Total Transversals in Hypergraphs and Their Applications ⋮ Total k-rainbow reinforcement number in graphs ⋮ Trees with large neighborhood total domination number ⋮ Double outer-independent domination number of graphs ⋮ Bounds on the domination number of a digraph and its reverse ⋮ Total Domination in Graphs with Diameter 2 ⋮ A linear-time algorithm for paired-domination on circular-arc graphs ⋮ Total dominator colorings and total domination in graphs ⋮ Disjunctive total domination in graphs ⋮ Total \([1,2\)-domination in graphs] ⋮ Game total domination for cycles and paths ⋮ Semitotal domination on AT-free graphs and circle graphs ⋮ On coupon coloring of Cartesian product of some graphs ⋮ New bounds on the double domination number of trees ⋮ Total and paired domination numbers of \(C_m\) bundles over a cycle \(C_n\) ⋮ Total restrained reinforcement in graphs ⋮ Matchings, path covers and domination ⋮ Algorithmic aspects of open neighborhood location-domination in graphs ⋮ On total domination in the Cartesian product of graphs ⋮ On the forcing domination and the forcing total domination numbers of a graph ⋮ Decreasing the maximum degree of a graph ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ An upper bound for the total restrained domination number of graphs ⋮ Total domination critical and stable graphs upon edge removal ⋮ Isolation of cycles ⋮ Total domination stable graphs upon edge addition ⋮ Graphs with disjoint dominating and paired-dominating sets ⋮ An improved upper bound on the total restrained domination number in cubic graphs ⋮ Girth and total domination in graphs ⋮ Isolation of \(k\)-cliques ⋮ Minimum size transversals in uniform hypergraphs ⋮ Total domination dot-critical graphs ⋮ A new lower bound for the total domination number in graphs proving a Graffiti.pc conjecture ⋮ On the algorithmic complexity of \(k\)-tuple total domination ⋮ Domination and total domination in cubic graphs of large girth ⋮ A maximum degree theorem for diameter-2-critical graphs ⋮ Total transversals and total domination in uniform hypergraphs ⋮ Total restrained domination in graphs of diameter 2 or 3 ⋮ Complexity of total outer-connected domination problem in graphs ⋮ Domination parameters of a graph and its complement ⋮ On the total \(k\)-domination in graphs ⋮ On 3-\(\gamma_t\)-vertex critical graphs of diameter three ⋮ On the complexity of the bondage and reinforcement problems ⋮ Multiple factor Nordhaus-Gaddum type results for domination and total domination ⋮ On \(\alpha\)-total domination in graphs ⋮ On graphs for which the connected domination number is at most the total domination number ⋮ A characterization of diameter-2-critical graphs with no antihole of length four ⋮ Edge lifting and total domination in graphs ⋮ Algorithm and hardness results on neighborhood total domination in graphs ⋮ Algorithm complexity of neighborhood total domination and \((\rho,\gamma_{\mathrm{nt}})\)-graphs ⋮ Vertices contained in all or in no minimum semitotal dominating set of a tree ⋮ Bounds on the disjunctive total domination number of a tree ⋮ Total domination versus domination in cubic graphs ⋮ A characterization of diameter-2-critical graphs whose complements are diamond-free ⋮ Locating-total domination in graphs ⋮ On the roman domination in the lexicographic product of graphs ⋮ Total domination versus paired-domination in regular graphs ⋮ On the existence of total dominating subgraphs with a prescribed additive hereditary property ⋮ On bondage numbers of graphs: a survey with some comments ⋮ A note on total reinforcement in graphs ⋮ Total domination changing and stable graphs upon vertex removal ⋮ Independent transversal total domination versus total domination in trees ⋮ Locating-total domination in claw-free cubic graphs ⋮ Transversals and domination in uniform hypergraphs ⋮ Global total \(k\)-domination: approximation and hardness results ⋮ On the semitotal domination number of line graphs ⋮ Total domination in plane triangulations ⋮ On a conjecture of Murty and Simon on diameter two critical graphs. II. ⋮ The maximum diameter of total domination edge-critical graphs ⋮ Perfect matchings in total domination critical graphs ⋮ Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs ⋮ Upper bounds on the \(k\)-forcing number of a graph ⋮ Algorithmic aspects of semitotal domination in graphs ⋮ On total \(f\)-domination: polyhedral and algorithmic results ⋮ A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free ⋮ \( K_{1 , 2}\)-isolation in graphs ⋮ On a class of graphs between threshold and total domishold graphs ⋮ Total domination edge critical graphs with total domination number three and many dominating pairs ⋮ Progress on the Murty-Simon conjecture on diameter-2 critical graphs: a survey ⋮ On the independence transversal total domination number of graphs ⋮ A note on \(\alpha\)-total domination in cubic graphs ⋮ Essential upper bounds on the total domination number ⋮ Coupon-coloring and total domination in Hamiltonian planar triangulations ⋮ On upper total domination versus upper domination in graphs ⋮ Bounds relating the weakly connected domination number to the total domination number and the matching number ⋮ On the existence of \(k\)-partite or \(K_p\)-free total domination edge-critical graphs ⋮ An extremal problem for total domination stable graphs upon edge removal ⋮ Total domination dot-stable graphs ⋮ Total forcing versus total domination in cubic graphs ⋮ Some progress on total bondage in graphs ⋮ Hardness results and approximation algorithm for total liar's domination in graphs ⋮ On a conjecture on total domination in claw-free cubic graphs ⋮ The total bondage number of grid graphs ⋮ A characterization of graphs with disjoint dominating and paired-dominating sets ⋮ Exact and heuristic algorithms for the weighted total domination problem ⋮ On the complexity of signed and minus total domination in graphs ⋮ Secure total domination in graphs: bounds and complexity ⋮ Partitioning the vertices of a cubic graph into two total dominating sets ⋮ Bounding the \(k\)-rainbow total domination number ⋮ Differentiating-total domination: approximation and hardness results ⋮ Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs ⋮ An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph ⋮ Admissible property of graphs in terms of radius ⋮ New bounds on the double total domination number of graphs ⋮ Total domination in inflated graphs ⋮ Total domination in partitioned graphs ⋮ Admissible property of graphs in terms of independence number ⋮ Total domination in planar graphs of diameter two
Uses Software
Cites Work
- Total domination and transformation
- Paired-domination in claw-free cubic graphs
- Total domination in claw-free graphs with minimum degree 2
- Ratios of some domination parameters in trees
- Bounds on total domination in claw-free cubic graphs
- On the upper total domination number of Cartesian products of graphs
- Total domination of graphs and small transversals of hypergraphs
- On the total domination number of cross products of graphs
- A new upper bound on the total domination number of a graph
- Total domination in graphs with given girth
- On domination problems for permutation and other graphs
- Total domination in interval graphs revisited
- Labeling algorithms for domination problems in sun-free chordal graphs
- Covering all cliques of a graph
- Dominating sets in perfect graphs
- Small transversals in hypergraphs
- The complexity of domination problems in circle graphs
- Relations between packing and covering numbers of a tree
- Linear algorithms on recursive representations of trees
- Optimal parallel algorithms on circular-arc graphs
- Total domination number of grid graphs
- On the total domination number of Cartesian products of graphs
- Transversal numbers of uniform hypergraphs
- Maximum sizes of graphs with given domination parameters
- Relating the size of a connected graph to its total and restricted domination numbers
- Vertices contained in all or in no minimum total dominating set of a tree
- The diameter of total domination vertex critical graphs
- Domination and total domination on asteroidal triple-free graphs
- Construction of trees and graphs with equal domination parameters
- On matching and total domination in graphs
- Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets
- Associative graph products and their independence, domination and coloring numbers
- Domination on Cocomparability Graphs
- Graph-theoretic parameters concerning domination, independence, and irredundance
- Easy problems for tree-decomposable graphs
- Erratum to: “A linear vizing-like relation relating the size and total domination number of a graph”
- Relationships between total domination, order, size, and maximum degree of graphs
- Hypergraphs with large transversal number and with edge sizes at least 3
- Total domination in 2-connected graphs and in graphs with no induced 6-cycles
- On the Algorithmic Complexity of Total Domination
- Total Domination and Irredundance in Weighted Interval Graphs
- Total domination in graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Upper total domination in claw‐free graphs
- Trees with unique minimum total dominating sets
- Some remarks on domination
- Graphs with large total domination number
- Domination in planar graphs with small diameter*
- Total Domination Edge Critical Graphs with Maximum Diameter
- Approximating theDomatic Number
- Domination numbers of planar graphs
- A linear Vizing‐like relation relating the size and total domination number of a graph
- Total Domination in Categorical Products of Graphs
- Upper total domination versus upper paired-domination
- A Transition from Total Domination in Graphs to Transversals in Hypergraphs
- Some results on total domination in direct products of graphs
- Parallel algorithms on circular-arc graphs
- Total domination in interval graphs
- Total domination in interval graphs
- Domination critical graphs
- Domination in distance-hereditary graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
