Paired-domination of trees

DOI10.1023/A:1021338214295zbMath1013.05055MaRDI 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)

Mathematics Subject Classification ID

05C05: Trees

05C75: Structural characterization of families of graphs

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

Related Items

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