Paired-domination in graphs
From MaRDI portal
Publication:4540077
DOI<199::AID-NET4>3.0.CO;2-F 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-FzbMath0997.05074OpenAlexW2003370404MaRDI QIDQ4540077
Teresa W. Haynes, Peter J. Slater
Publication date: 21 July 2002
Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199810)32:3<199::aid-net4>3.0.co;2-f
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
γ-paired dominating graphs of cycles ⋮ Semipaired Domination in Some Subclasses of Chordal Graphs ⋮ Paired-Domination Game Played in Graphs ⋮ Paired domination stability in graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Algorithmic aspects of paired disjunctive domination in graphs ⋮ Complexity of paired domination in at-free and planar graphs ⋮ Paired-domination game played on cycles ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Linear-time algorithm for paired-domination on distance-hereditary graphs ⋮ The Outer-Paired Domination of Graphs ⋮ γ-Paired dominating graphs of lollipop, umbrella and coconut graphs ⋮ Unnamed Item ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Complexity of the paired domination subdivision problem ⋮ Unicyclic graphs with strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers ⋮ Complexity and algorithms for semipaired domination in graphs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ My Favorite Domination Conjectures in Graph Theory Are Bounded ⋮ Open-independent, open-locating-dominating sets ⋮ Outer-paired domination in graphs ⋮ Upper paired domination versus upper domination ⋮ Strong equality of Roman and weak Roman domination in trees ⋮ Computing a minimum paired-dominating set in strongly orderable graphs ⋮ Upper bounds for the paired-domination numbers of graphs ⋮ Total and paired domination numbers of \(C_m\) bundles over a cycle \(C_n\) ⋮ Paired-domination subdivision numbers of graphs ⋮ Unnamed Item ⋮ The paired-domination and the upper paired-domination numbers of graphs ⋮ Paired-domination in claw-free graphs ⋮ Paired domination on interval and circular-arc graphs ⋮ Bounds on domination parameters in graphs: a brief survey ⋮ Paired domination in trees ⋮ Upper bounds on the paired domination subdivision number of a graph ⋮ Graphs with large paired-domination number ⋮ Paired domination versus domination and packing number in graphs ⋮ Complexity of paired domination in AT-free and planar graphs ⋮ Paired-domination in inflated graphs ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ Paired-domination in subdivided star-free graphs ⋮ Dominating direct products of graphs ⋮ Graphs with disjoint dominating and paired-dominating sets ⋮ Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs ⋮ Semipaired domination in claw-free cubic graphs ⋮ Vertices in all minimum paired-dominating sets of block graphs ⋮ Domination parameters with number 2: interrelations and algorithmic consequences ⋮ Graphs with large semipaired domination number ⋮ Cubic graphs have paired-domination number at most four-seventh of their orders ⋮ Distance paired domination numbers of graphs ⋮ A note on domination and total domination in prisms ⋮ On graphs for which the connected domination number is at most the total domination number ⋮ Perfect matchings in paired domination vertex critical graphs ⋮ \(H\)-domination in graphs ⋮ Total domination versus paired-domination in regular graphs ⋮ On bondage numbers of graphs: a survey with some comments ⋮ Total and paired domination numbers of toroidal meshes ⋮ 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 ⋮ Ratios of some domination parameters in trees ⋮ Paired-domination in claw-free graphs with minimum degree at least three ⋮ 2-distance paired-dominating number of graphs ⋮ Paired-domination in generalized claw-free graphs ⋮ On the distance paired domination of generalized Petersen graphs \(P(n,1)\) and \(P(n,2)\) ⋮ (Total) domination in prisms ⋮ 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 ⋮ A characterization of cubic graphs with paired-domination number three-fifths their order ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Which trees have a differentiating-paired dominating set? ⋮ Paired-domination number of claw-free odd-regular graphs ⋮ Paired versus double domination in \(K_{1,r}\)-free graphs ⋮ An upper bound on the paired-domination number in terms of the number of edges in the graph ⋮ Well paired-dominated graphs ⋮ Labelling algorithms for paired-domination problems in block and interval graphs ⋮ Characterizations of trees with equal paired and double domination numbers ⋮ A characterization of graphs with disjoint dominating and paired-dominating sets ⋮ Upper paired-domination in claw-free graphs ⋮ Bounds on the semipaired domination number of graphs with minimum degree at least two ⋮ A greedy algorithm for the fault-tolerant outer-connected dominating set problem ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ Perfect graphs involving semitotal and semipaired domination ⋮ Domination related parameters in the generalized lexicographic product of graphs ⋮ Strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers in trees ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ Vertices contained in all or in no minimum paired-dominating set of a tree ⋮ Combinatorial bounds on paired and multiple domination in triangulations ⋮ Paired-domination number of a graph and its complement ⋮ Paired bondage in trees ⋮ Minimum 2-tuple dominating set of permutation graphs ⋮ Tightness of domination inequalities for direct product graphs ⋮ Upper bounds on the paired-domination number ⋮ Vertices contained in all minimum paired-dominating sets of a tree ⋮ 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 ⋮ A note on the upper bound for the paired-domination number of a graph with minimum degree at least two ⋮ Paired-domination in \(P_{5}\)-free graphs ⋮ Paired domination vertex critical graphs ⋮ Varieties of Roman Domination ⋮ Paired Domination in Graphs ⋮ Bounds on the paired domination number of graphs with minimum degree at least three ⋮ Dominating sets and domination polynomials of paths ⋮ Graph Critical With Respect To Independent Domination ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ 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 ⋮ Some Parameters on Neighborhood Number of A Graph ⋮ Vizing's conjecture: a survey and recent results ⋮ Total restrained domination in cubic graphs ⋮ Critical paired dominating sets and irreducible decompositions of powers of edge ideals ⋮ Semipaired domination in maximal outerplanar graphs ⋮ Total and paired domination numbers of cylinders ⋮ Corona domination number of graphs ⋮ Locating-paired-dominating sets in square grids ⋮ Paired-domination of Cartesian products of graphs and rainbow domination ⋮ Unique minimum semipaired dominating sets in trees ⋮ CONNECTED LIAR'S DOMINATION IN GRAPHS: COMPLEXITY AND ALGORITHMS ⋮ A linear-time algorithm for paired-domination on circular-arc graphs ⋮ A proof of a conjecture on the paired-domination subdivision number
