Paired-domination of trees

DOI10.1023/A:1021338214295zbMath1013.05055OpenAlexW116975680MaRDI QIDQ1810885

Ding-Zhu Du, Mihaela Cardei, Hong Qiao, Li-ying Kang

Publication date: 9 June 2003

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1021338214295

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Paired-domination subdivision numbers of graphs ⋮ Paired-domination in claw-free graphs ⋮ Paired domination on interval and circular-arc graphs ⋮ Graphs with large paired-domination number ⋮ Paired-domination in inflated graphs ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ Graphs with disjoint dominating and paired-dominating sets ⋮ Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs ⋮ Vertices in all minimum paired-dominating sets of block graphs ⋮ Linear-time algorithm for paired-domination on distance-hereditary graphs ⋮ On bondage numbers of graphs: a survey with some comments ⋮ A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph ⋮ Graphs with maximum size and given paired-domination number ⋮ A characterization of \((2\gamma ,\gamma _{\text p})\)-trees ⋮ Paired-domination in claw-free graphs with minimum degree at least three ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Paired-domination in generalized claw-free graphs ⋮ On the distance paired domination of generalized Petersen graphs \(P(n,1)\) and \(P(n,2)\) ⋮ Complexity of distance paired-domination problem in graphs ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Locating and paired-dominating sets in graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Which trees have a differentiating-paired dominating set? ⋮ An upper bound on the paired-domination number in terms of the number of edges in the graph ⋮ Labelling algorithms for paired-domination problems in block and interval graphs ⋮ A characterization of graphs with disjoint dominating and paired-dominating sets ⋮ Upper paired-domination in claw-free graphs ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ Vertices contained in all or in no minimum paired-dominating set of a tree ⋮ Paired bondage in trees ⋮ Minimum 2-tuple dominating set of permutation graphs ⋮ A polynomial-time algorithm for the paired-domination problem on permutation graphs ⋮ Domination parameters in coronene torus network ⋮ The diameter of paired-domination vertex critical graphs ⋮ Paired Domination in Graphs ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Constructive characterizations of \( (\gamma_p,\gamma)\)-and \( (\gamma_p, \gamma_{pr})\)-trees ⋮ Hardness results and approximation algorithms for (weighted) paired-domination in graphs ⋮ Distance paired-domination problems on subclasses of chordal graphs ⋮ Outer-paired domination in graphs ⋮ A linear-time algorithm for paired-domination on circular-arc graphs